1.1.1. 各领域系统的共性问题

1.1.1. Common Problems of Systems in Many Fields

在这些种类的系统中遇到的问题可以分为四类：突发属性、影响传播、不相称的扩展和权衡。

The problems one encounters in these many kinds of systems can usefully be divided into four categories: emergent properties, propagation of effects, incommensurate scaling, and trade-offs.

1.1.2. 系统、组件、接口和环境

1.1.2. Systems, Components, Interfaces, and Environments

韦氏第三版新国际词典未删节版将系统定义为“由许多通常不同的部分组成的复杂整体，这些部分服从于一个共同的计划或服务于一个共同的目的”。虽然这个定义在日常使用中已经足够，但工程师通常更喜欢更具体一些的定义。我们将“许多通常不同的部分”称为“组件”。我们通过组件的互连来识别“整体”和“共同计划” ，并将系统的“共同目的”视为在其与环境的接口上表现出某种行为。因此，我们制定了技术定义：系统是一组互连的组件，其在与环境的接口上具有预期的行为。

Webster’s Third New International Dictionary, Unabridged, defines a system as “a complex unity formed of many often diverse parts subject to a common plan or serving a common purpose.” Although this definition will do for casual use of the word, engineers usually prefer something a bit more concrete. We identify the “many often diverse parts” by naming them components. We identify the “unity” and “common plan” with the interconnections of the components, and we perceive the “common purpose” of a system to be to exhibit a certain behavior across its interface to an environment. Thus we formulate our technical definition: A system is a set of interconnected components that has an expected behavior observed at the interface with its environment.

系统概念的基本思想是将世界上的所有事物分为两类：正在讨论的事物和未讨论的事物。正在讨论的事物是系统的一部分，未讨论的事物是环境的一部分。例如，我们可以将太阳系定义为由太阳、行星、小行星和彗星组成。太阳系的环境是宇宙的其余部分。（事实上，“宇宙”一词是环境的同义词。）

The underlying idea of the concept of system is to divide all the things in the world into two groups: those under discussion and those not under discussion. Those things under discussion are part of the system—those that are not are part of the environment. For example, we might define the solar system as consisting of the sun, planets, asteroids, and comets. The environment of the solar system is the rest of the universe. (Indeed, the word “universe” is a synonym for environment.)

系统与其环境之间总是存在相互作用；这些相互作用是系统与环境之间的界面。太阳系与宇宙其他部分之间的界面包括对最近恒星的引力吸引和电磁辐射交换。个人计算机的主要界面通常包括显示器、键盘、扬声器、网络连接和电源线等，但也有不太明显的界面，例如大气压力、环境温度和湿度以及电磁噪声环境。

There are always interactions between a system and its environment; these interactions are the interface between the system and the environment. The interface between the solar system and the rest of the universe includes gravitational attraction for the nearest stars and the exchange of electromagnetic radiation. The primary interfaces of a personal computer typically include things such as a display, keyboard, speaker, network connection, and power cord, but there are also less obvious interfaces such as the atmospheric pressure, ambient temperature and humidity, and the electromagnetic noise environment.

人们研究一个系统是为了根据其组件、组件之间的相互联系以及各个组件的行为来预测其整体行为。然而，识别组件取决于人们的观点，它包括两个方面：目的和粒度。人们可能出于不同的目的，以完全不同的方式看待一个系统。人们也可以选择几种不同的粒度。这些选择对人们识别系统组件有重要影响。

One studies a system to predict its overall behavior, based on information about its components, their interconnections, and their individual behaviors. Identifying the components, however, depends on one’s point of view, which has two aspects, purpose and granularity. One may, with different purposes in mind, look at a system quite differently. One may also choose any of several different granularities. These choices affect one’s identification of the components of the system in important ways.

要了解观点如何取决于目的，请考虑将喷气式飞机视为一个系统的两种观点。第一种观点将飞机视为飞行物体，其中系统的组件包括机身、机翼、控制面和发动机。环境是大气和地球，界面由重力、发动机推力和空气阻力组成。第二种观点将飞机视为乘客处理系统。现在，组件包括座椅、乘务员、空调系统和厨房。环境是一组乘客，界面是座椅的柔软度、餐食和从空调系统流出的空气。

To see how point of view can depend on purpose, consider two points of view of a jet aircraft as a system. The first looks at the aircraft as a flying object, in which the components of the system include the body, wings, control surfaces, and engines. The environment is the atmosphere and the earth, with interfaces consisting of gravity, engine thrust, and air drag. A second point of view looks at the aircraft as a passenger-handling system. Now, the components include seats, flight attendants, the air conditioning system, and the galley. The environment is the set of passengers, and the interfaces are the softness of the seats, the meals, and the air flowing from the air conditioning system.

从第一种观点来看，飞机是一个飞行物体，有座椅、乘务员和厨房，但设计师主要将它们视为重量的贡献者。相反，从第二种观点来看，飞机是一个乘客处理系统，设计师将发动机视为噪音源，也可能是废气源，并可能忽略机翼上的控制面。因此，根据不同的观点，我们可能会选择忽略或合并某些系统组件或接口。

In the first point of view, the aircraft as a flying object, the seats, flight attendants, and galley were present, but the designer considers them primarily as contributors of weight. Conversely, in the second point of view, as a passenger-handling system, the designer considers the engine as a source of noise and perhaps also exhaust fumes, and probably ignores the control surfaces on the wings. Thus, depending on point of view, we may choose to ignore or consolidate certain system components or interfaces.

选择粒度的能力意味着，在一种情况下，组件可能是另一种情况下的整个系统。从飞机设计师的角度来看，喷气发动机是一个提供重量、推力甚至阻力的部件。另一方面，发动机制造商将其视为一个独立的系统，它有许多部件——涡轮机、液压泵、轴承、加力燃烧器，所有这些部件都以各种方式相互作用以产生推力——一个与发动机环境的接口。支撑发动机的机翼是飞机系统的一个部件，但它是发动机系统环境的一部分。

The ability to choose granularity means that a component in one context may be an entire system in another. From an aircraft designer’s point of view, a jet engine is a component that contributes weight, thrust, and perhaps drag. On the other hand, the manufacturer of the engine views it as a system in its own right, with many components—turbines, hydraulic pumps, bearings, afterburners, all of which interact in diverse ways to produce thrust—one interface with the environment of the engine. The airplane wing that supports the engine is a component of the aircraft system, but it is part of the environment of the engine system.

如果一个系统在某种情况下是另一个情况下的组件，则通常将其称为子系统（但请参见边栏 1.3）。由子系统组成系统或将系统分解为子系统可以进行到尽可能多的层次。

When a system in one context is a component in another, it is usually called a subsystem (but see Sidebar 1.3). The composition of systems from subsystems or decomposition of systems into subsystems can be carried on to as many levels as is useful.

总而言之，要分析一个系统，就必须建立一个观点来确定哪些东西可以视为组件，这些组件的粒度应该是多少，系统的边界在哪里，以及系统与其环境之间的哪些接口是感兴趣的。

In summary, then, to analyze a system one must establish a point of view to determine which things to consider as components, what the granularity of those components should be, where the boundary of the system lies, and which interfaces between the system and its environment are of interest.

在我们使用的术语中，计算机系统或信息系统是一种旨在自动控制下存储、处理或传达信息的系统。此外，我们对以数字为主的系统感兴趣。以下是一些示例：

As we use the term, a computer system or an information system is a system intended to store, process, or communicate information under automatic control. Further, we are interested in systems that are predominantly digital. Here are some examples:

同时，我们有时会发现，看看非数字和非自动化信息处理系统的例子（例如邮局或图书馆），以获得想法和指导很有用。

At the same time we will sometimes find it useful to look at examples of nondigital and nonautomated information handling systems, such as the post office or library, for ideas and guidance.

1.1.3. 复杂性

1.1.3. Complexity

韦氏词典对“系统”的定义使用了“复杂”一词。查找该术语，我们发现复杂意味着“难以理解”。缺乏系统理解是复杂性的根本特征。因此，复杂性既是一个主观概念，也是一个相对概念。也就是说，人们可以认为一个系统比另一个系统更复杂，但即使人们可以统计出似乎导致复杂性的各种因素，也没有统一的衡量标准。即使一个系统比另一个系统更复杂的论点也很难令人信服——同样是因为缺乏统一的衡量标准。我们可以借用医学中的一种技术来代替这种衡量标准：描述一组有助于确认诊断的复杂性迹象。作为必然结果，我们放弃了对复杂性进行明确描述的希望。我们必须寻找它的迹象，如果出现足够多的迹象，就认为复杂性是存在的。为此，以下是复杂性的五个迹象：

Webster’s definition of “system” used the word “complex”. Looking up that term, we find that complex means “difficult to understand”. Lack of systematic understanding is the underlying feature of complexity. It follows that complexity is both a subjective and a relative concept. That is, one can argue that one system is more complex than another, but even though one can count up various things that seem to contribute to complexity, there is no unified measure. Even the argument that one system is more complex than another can be difficult to make compelling—again because of the lack of a unified measure. In place of such a measure, we can borrow a technique from medicine: describe a set of signs of complexity that can help confirm a diagnosis. As a corollary, we abandon hope of producing a definitive description of complexity. We must instead look for its signs, and if enough appear, argue that complexity is present. To that end, here are five signs of complexity:

再举一个例子来说明这一点：对比一下小镇图书馆和大型大学图书馆。两者在规模上明显存在差异：大学图书馆的藏书更多，因此存在第一个迹象。第二个迹象更微妙：小型图书馆可能有目录来指导用户，而大学图书馆可能不仅有目录，还有检索工具、读者指南、文摘服务、期刊索引等。虽然这些细节使大型图书馆更有用（至少对有经验的用户而言），但它们也使向图书馆添加新项目的任务变得复杂：必须有人添加许多互连（在这种情况下是交叉引用），以便能够以所有预期的方式找到新项目。第三个迹象，即大量例外情况，也很明显。小型图书馆只有少数分类（小说、传记、非小说和杂志）和少数例外情况（超大书籍放在报刊架上），而大学图书馆则充斥着例外情况。有些书是超大尺寸的，有些是缩微胶卷或数字媒体的，有些书是稀有或有价值的，必须加以保护，有些书讲解如何制造氢弹，只能借给某些读者，有些书无法在任何标准分类系统中编目。至于第四个迹象，任何大型大学图书馆的用户都会确认，没有系统规则来查找信息，图书馆的使用是一门艺术，而不是一门科学。

Again, an example can illustrate: contrast a small-town library with a large university library. There is obviously a difference in scale: the university has more books, so the first sign is present. The second sign is more subtle: where the small library may have a catalog to guide the user, the university library may have not only a catalog, but also finding aids, readers’ guides, abstracting services, journal indexes, and so on. Although these elaborations make the large library more useful (at least to the experienced user), they also complicate the task of adding a new item to the library: someone must add many interconnections (in this case, cross-references) so that the new item can be found in all the intended ways. The third sign, a large number of exceptions, is also apparent. Where the small library has only a few classifications (fiction, biography, nonfiction, and magazines) and a few exceptions (oversized books are kept over the newspaper rack), the university library is plagued with exceptions. Some books are oversized, others come on microfilm or on digital media, some books are rare or valuable and must be protected, the books that explain how to build a hydrogen bomb can be loaned only to certain patrons, some defy cataloging in any standard classification system. As for the fourth sign, any user of a large university library will confirm that there are no methodical rules for locating a piece of information and that library usage is an art, not a science.

最后，第五个复杂标志是拥有多名员工，这在大学图书馆中尤为明显。许多小城镇实际上只有一名图书管理员——通常是一个精力充沛的人，熟悉每本书，因为他或她曾经有机会接触过这些书——而大学图书馆不仅拥有许多工作人员，甚至还有只熟悉图书馆运营某一方面的专家，例如微缩胶片收藏。

Finally, the fifth sign of complexity, a staff of more than one person, is evident in the university library. Where many small towns do in fact have just one librarian—typically an energetic person who knows each book because at one time or another he or she has had occasion to touch it—the university library has not only many personnel, but even specialists who are familiar with only one facet of library operations, such as the microform collection.

大学图书馆展现了复杂性的所有五个特征，但一致性并不是必不可少的。另一方面，仅存在一个或两个特征可能无法令人信服地证明复杂性。热力学中考虑的系统包含数量惊人的成分（基本粒子）和相互作用，但从正确的角度来看，它们并不算复杂，因为它们的行为有简单、有条理的描述。正是当我们缺乏这样一种简单、有条理的描述时，我们才具有复杂性。

The university library exhibits all five signs of complexity, but unanimity is not essential. On the other hand, the presence of only one or two of the signs may not make a compelling case for complexity. Systems considered in thermodynamics contain an unthinkably large number of components (elementary particles) and interactions, yet from the right point of view they do not qualify as complex because there is a simple, methodical description of their behavior. It is exactly when we lack such a simple, methodical description that we have complexity.

有人反对将复杂性视为基于这五个迹象，认为所有系统都是无限复杂的，甚至可能是无限复杂的，因为挖掘得越深，就会出现越多的复杂性迹象。因此，即使是最简单的数字计算机也是由门组成的，门由晶体管组成，晶体管由硅组成，硅由质子、中子和电子组成，电子由夸克组成，一些物理学家认为夸克可以描述为振动的弦，等等。我们稍后将通过限制挖掘深度（一种称为抽象的技术）来解决这一反对意见。我们感兴趣和担心的复杂性是尽管使用了抽象，但仍然存在的复杂性。

One objection to conceiving complexity as being based on the five signs is that all systems are indefinitely, perhaps infinitely, complex because the deeper one digs the more signs of complexity turn up. Thus, even the simplest digital computer is made of gates, which are made with transistors, which are made of silicon, which is composed of protons, neutrons, and electrons, which are composed of quarks, which some physicists suggest are describable as vibrating strings, and so on. We shall address this objection in a moment by limiting the depth of digging, a technique known as abstraction. The complexity that we are interested in and worried about is the complexity that remains despite the use of abstraction.

1.2.1. 级联和交互需求

1.2.1. Cascading and Interacting Requirements

复杂性的主要来源就是系统的需求列表。从自身来看，每个需求似乎都很简单。任何特定需求甚至可能只会给现有需求列表增加易于容忍的复杂性。问题是，许多需求的积累不仅增加了它们各自的复杂性，还增加了它们相互作用的复杂性。这种相互作用的复杂性源于对通用性和例外情况的压力，这些情况增加了复杂性，而随着时间的推移，个别需求的变化使情况变得更糟。

A primary source of complexity is just the list of requirements for a system. Each requirement, viewed by itself, may seem straightforward. Any particular requirement may even appear to add only easily tolerable complexity to an existing list of requirements. The problem is that the accumulation of many requirements adds not only their individual complexities but also complexities from their interactions. This interaction complexity arises from pressure for generality and exceptions that add complications, and it is made worse by change in individual requirements over time.

到目前为止，大多数个人计算机用户都遇到过以下场景：供应商宣布发布您用来管理支票簿的程序的新版本，新版本具有一些似乎很重要或有用的功能（例如，它可以处理最新的在线银行系统），因此您订购了该程序。在尝试安装它时，您发现这个新版本需要某个共享库包的较新版本。您找到该较新版本并进行安装，却发现库包需要较新版本的操作系统，而您之前没有任何理由安装该操作系统。您忍痛安装了最新版本的操作系统，现在支票簿程序可以正常工作，但您的附加硬盘开始出现问题。经调查发现，磁盘供应商的专有软件与新操作系统版本不兼容。不幸的是，磁盘供应商仍在调试磁盘软件的更新，最好的可用版本是月底将到期的 beta 测试版。

Most users of a personal computer have by now encountered some version of the following scenario: The vendor announces a new release of the program you use to manage your checkbook, and the new release has some feature that seems important or useful (e.g., it handles the latest on-line banking systems), so you order the program. Upon trying to install it, you discover that this new release requires a newer version of some shared library package. You track down that newer version and install it, only to find that the library package requires a newer version of the operating system, which you had not previously had any reason to install. Biting the bullet, you install the latest release of the operating system, and now the checkbook program works, but your add-on hard disk begins to act flaky. On investigation it turns out that the disk vendor’s proprietary software is incompatible with the new operating system release. Unfortunately, the disk vendor is still debugging an update for the disk software, and the best thing available is a beta test version that will expire at the end of the month.

造成这种情况的根本原因是个人计算机的设计满足了许多要求：组织良好的文件系统、存储的可扩展性、连接各种 I/O 设备的能力、网络连接、保护网络中其他位置免受恶意人员的攻击、可用性、可靠性、低成本——不胜枚举。这些要求中的每一个都增加了自身的复杂性，而它们之间的相互作用又增加了更多的复杂性。

The underlying cause of this scenario is that the personal computer has been designed to meet many requirements: a well-organized file system, expandability of storage, ability to attach a variety of I/O devices, connection to a network, protection from malevolent persons elsewhere in the network, usability, reliability, low cost—the list goes on and on. Each of these requirements adds complexity of its own, and the interactions among them add still more complexity.

同样，多年来，电话系统也获得了大量的线路定制功能 - 呼叫等待、回拨、呼叫转接、发起和终止呼叫阻止、反向计费、来电显示、来电显示阻止、拒绝匿名呼叫、请勿打扰、休假保护 - 再次，这个列表可以很长。这些功能以多种方式相互作用，以至于电话系统中存在一个“功能交互”的研究领域。这项研究始于对应该发生什么的争论。例如，所谓的 900 号码具有称为反向计费的功能 - 被叫方可以在呼叫者的账单上收取费用。爱丽丝（爱丽丝是我们在侧边栏 1.4中描述的角色阵容中遇到的第一个角色）具有阻止拨出到反向计费号码的呼叫的功能。爱丽丝呼叫鲍勃，鲍勃的电话被转接到 900 号码。电话应该接通吗？如果是，哪一方应该付费，鲍勃还是爱丽丝？有三个相互作用的功能和至少四种不同的可能性：阻止呼叫、允许呼叫并向 Bob 收费、响铃 Bob 的电话，或者添加另一个功能（每月收费）让 Bob 选择结果。

Similarly, the telephone system has, over the years, acquired a large number of line customizing features—call waiting, call return, call forwarding, originating and terminating call blocking, reverse billing, caller ID, caller ID blocking, anonymous call rejection, do not disturb, vacation protection—again, the list goes on and on. These features interact in so many ways that there is a whole field of study of “feature interaction” in telephone systems. The study begins with debates over what should happen. For example, so-called 900 numbers have the feature called reverse billing—the called party can place a charge on the caller’s bill. Alice (Alice is the first character we have encountered in our cast of characters, described in Sidebar 1.4) has a feature that blocks outgoing calls to reverse billing numbers. Alice calls Bob, whose phone is forwarded to a 900 number. Should the call go through, and if so, which party should pay for it, Bob or Alice? There are three interacting features, and at least four different possibilities: block the call, allow the call and charge it to Bob, ring Bob’s phone, or add yet another feature that (for a monthly fee) lets Bob choose the outcome.

这些例子表明，其中存在一个基本原则。我们称之为：

The examples suggest that there is an underlying principle at work. We call it the:

这个原则是主观的，因为复杂性本身就是主观的——其大小取决于观察者的想法。图 1.1提供了该原则的图形解释。在研究这个图时，也许最重要的是要认识到复杂性障碍是软性的：当你添加功能和需求时，你不会遇到一个坚实的障碍来警告你停止添加。情况只会变得更糟。

The principle is subjective because complexity itself is subjective—its magnitude is in the mind of the beholder. Figure 1.1 provides a graphical interpretation of the principle. Perhaps the most important thing to recognize in studying this figure is that the complexity barrier is soft: as you add features and requirements, you don’t hit a solid roadblock to warn you to stop adding. It just gets worse.

图 1.1复杂性升级原则。

Figure 1.1 The principle of escalating complexity.

随着要求数量的增加，例外情况的数量也会增加，因此复杂性也会增加。美国税法中特殊情况的数量令人难以置信，这使填写所得税申报表成为一项复杂的工作。任何一项例外的影响可能很小，但许多相互作用的例外累积起来的影响会使系统变得非常复杂，以致没有人能够理解它。复杂性还可能来自外部要求，比如坚持某种部件必须来自某个特定供应商。该部件可能不如其他供应商的耐用性好、更重或不那么容易买到。这些特性可能不会妨碍其使用，但它们增加了系统其他部分的复杂性，而系统其他部分必须进行设计来弥补这些复杂性。

As the number of requirements grows, so can the number of exceptions and thus the complications. It is the incredible number of special cases in the United States tax code that makes filling out an income tax return a complex job. The impact of any one exception may be minor, but the cumulative impact of many interacting exceptions can make a system so complex that no one can understand it. Complications also can arise from outside requirements such as insistence that a certain component must come from a particular supplier. That component may be less durable, heavier, or not as available as one from another supplier. Those properties may not prevent its use, but they add complexity to other parts of the system that have to be designed to compensate.

用单一设计满足多种需求有时被表达为对通用性的需求。通用性可以宽泛地定义为“适用于各种情况”。不幸的是，通用性会增加复杂性，因此它需要权衡，设计师必须运用良好的判断力来决定真正需要多少通用性。举一个极端的例子，一辆有四个独立方向盘的汽车，每个方向盘控制一个轮胎，提供了某种终极通用性，但几乎所有这些通用性都是不受欢迎的。在这里，不受欢迎的方面和由此产生的汽车导航复杂性都很明显，但在许多情况下，这两个方面都更难评估：一种提议的通用性形式在多大程度上使系统复杂化，这种通用性在多大程度上真正有用？不受欢迎的通用性也会间接增加复杂性：具有过度通用性的系统的用户将采用简化和抑制他们不需要的通用性的使用方式。不同的用户可能会采用不同的方式，然后发现他们无法轻松地相互交换想法。任何试图使用别人定制的个人电脑的人都会注意到这个问题。

Meeting many requirements with a single design is sometimes expressed as a need for generality. Generality may be loosely defined as “applying to a variety of circumstances.” Unfortunately, generality contributes to complexity, so it comes with a trade-off, and the designer must use good judgment to decide how much of the generality is actually wanted. As an extreme example, an automobile with four independent steering wheels, each controlling one tire, offers some kind of ultimate in generality, almost all of which is unwanted. Here, both the aspect of unwantedness and the resulting complexity of guidance of the auto are obvious enough, but in many cases both of these aspects are more difficult to assess: How much does a proposed form of generality complicate the system, and to what extent is that generality really useful? Unwanted generality also contributes to complexity indirectly: users of a system with excessive generality will adopt styles of usage that simplify and suppress generality that they do not need. Different users may adopt different styles and then discover that they cannot easily exchange ideas with one another. Anyone who tries to use a personal computer customized by someone else will notice this problem.

时不时地，有人会尝试设计一种可以在高速公路上行驶、飞行和用作船的交通工具，但这种通用设计的结果似乎在任何预期的交通方式中都无法很好地发挥作用。为了帮助对抗过度的通用性，经验表明了另一项设计原则：^*

Periodically, someone tries to design a vehicle that one can drive on the highway, fly, and use as a boat, but the result of such a general design does not seem to work well in any of the intended modes of transport. To help counter excessive generality, experience suggests another design principle:^*

例外和普遍性之间存在着矛盾。设计子系统的艺术之一就是使其功能足够普遍，以尽量减少必须作为特殊情况处理的例外数量。这是系统设计师判断力最明显的领域。

There is a tension between exceptions and generality. Part of the art of designing a subsystem is to make its features general enough to minimize the number of exceptions that must be handled as special cases. This area is one where the judgment of the system designer is most evident.

抵消不相称的扩展效应可能是复杂性的另一个来源。霍尔丹在他的文章“论合适的尺寸”中指出，昆虫等小型生物通过皮肤吸收足够的氧气以生存，但较大的生物需要的氧气量与其线性尺寸的立方成正比，没有足够的表面积。为了弥补这种不相称的扩展，它们增加了肺和血管的复杂性，以吸收和输送氧气到全身。以计算机为例，控制烤面包机的 4 位微处理器的程序员可以在几天内成功地用二进制数字编写所需的代码，而使用 64 位处理器和 40 GB 支持数据的视频游戏的程序员需要大量工具——编译器、图像或视频编辑器、特效生成器等，以及操作系统，才能在一生中完成工作。不相称的扩展需要使用一套更为复杂的工具。

Counteracting the effects of incommensurate scaling can be an additional source of complexity. Haldane, in his essay “On being the right size”, points out that small organisms such as insects absorb enough oxygen to survive through their skins, but larger organisms, which require an amount of oxygen proportional to the cube of their linear size, don’t have enough surface area. To compensate for this incommensurate scaling, they add complexity in the form of lungs and blood vessels to absorb and deliver oxygen throughout their bodies. In the case of computers, the programmer of a 4-bit microprocessor to control a toaster can in a few days successfully write the needed code entirely with binary numbers, while the programmer of a video game with a 64-bit processor and 40 gigabytes of supporting data requires an extensive array of tools—compilers, image or video editors, special effects generators, and the like, as well as an operating system, to be able to get the job done within a lifetime. Incommensurate scaling has required employment of a far more complex set of tools.

最后，复杂性的一个主要来源是需求的变化。成功的系统设计通常会长期使用，在此期间系统的环境会发生变化。硬件技术的改进可能会导致系统维护人员想要升级到更快、更便宜或更可靠的设备。同时，有关如何维护旧设备（以及备件供应）的知识可能会消失。随着用户对系统经验的积累，会越来越清楚地认识到，一些额外的要求应该是设计的一部分，而一些原始要求并不像最初想象的那么重要。系统规模通常会扩大，有时会远远超出其原始设计者的设想。

Finally, a major source of complexity is that requirements change. System designs that are successful usually remain in use for a long time, during which the environment of the system changes. Improvements in hardware technology may lead the system maintainers to want to upgrade to faster, cheaper, or more reliable equipment. Meanwhile, knowledge of how to maintain the older equipment (and the supply of spare parts) may be disappearing. As users accumulate experience with the system, it becomes clearer that some additional requirements should have been part of the design and that some of the original requirements were less important than originally thought. Often a system will expand in scale, sometimes far beyond the vision of its original designers.

在每种情况下，最初设计人员开发系统时所采用的基本规则和假设都开始失去其意义。系统设计人员可能已经预见到一些环境变化，但可能还存在一些他们没有预料到的变化。为了满足不可预见的需求而发生的变更通常会增加复杂性。由于更改已部署系统的架构可能很困难（第 1.3 节解释了原因），因此人们有强烈的动机在现有架构内进行更改，无论这是否是最好的选择。影响的传播可能会放大由变更引起的问题，因为变更的更远的影响可能直到有人调用某些很少使用的功能时才会被注意到。当这些远距离影响最终浮现时，维护人员可能会再次发现最简单的方法是在本地处理它们，也许是通过添加例外。当后来的维护人员扩大系统规模或用更快的硬件替换基础时，不相称的扩展效应开始主导行为。同样，对这些影响的第一个反应通常是进行局部更改（有时称为补丁）来抵消它们，而不是进行需要更改多个模块或更改模块之间接口的根本设计更改。

In each of these cases, the ground rules and assumptions that the original designers used to develop the system begin to lose their relevance. The system designers may have foreseen some environmental changes, but there were other changes they probably did not anticipate. As changes to meet unforeseen requirements occur, they usually add complexity. Because it can be difficult to change the architecture of a deployed system (Section 1.3 explains why), there is a powerful incentive to make changes within the existing architecture, whether or not that is the best thing to do. Propagation of effects can amplify the problems caused by change because more distant effects of a change may not be noticed until someone invokes some rarely used feature. When those distant effects finally do surface, the maintainer may again find it easiest to deal with them locally, perhaps by adding exceptions. Incommensurate scaling effects begin to dominate behavior when a later maintainer scales a system up in size or replaces the underpinnings with faster hardware. Again, the first response to these effects is usually to make local changes (sometimes called patches) to counteract them rather than to make fundamental changes in design that would require changing several modules or changing interfaces between modules.

一个密切相关的问题是，随着时间的推移，系统的复杂性不断增加，即使是最简单的更改（例如修复错误）也有可能引入另一个错误，因为复杂性往往会掩盖修复的全部影响。旧系统中的一个常见现象是，错误修复版本引入的错误数量可能超过该版本修复的错误数量。^*

A closely related problem is that as systems grow in complexity with the passage of time, even the simplest change, such as to repair a bug, has an increasing risk of introducing another bug because complexity tends to obscure the full impact of the repair. A common phenomenon in older systems is that the number of bugs introduced by a bug fix release may exceed the number of bugs fixed by that release.^*

最重要的是，随着系统老化，它们会逐渐积累变化，使其变得更加复杂。系统的寿命通常受其复杂性的限制，复杂性会随着系统的发展越来越偏离其原始设计而不断积累。

The bottom line is that as systems age, they tend to accumulate changes that make them more complex. The lifetime of a system is usually limited by the complexity that accumulates as it evolves farther and farther from its original design.

1.2.2. 保持高利用率

1.2.2. Maintaining High Utilization

一个需求本身往往是复杂性的一个特定来源。它始于对高性能或高效率的渴望。每当涉及稀缺资源时，就会努力保持其高利用率。

One requirement by itself is frequently a specific source of complexity. It starts with a desire for high performance or high efficiency. Whenever a scarce resource is involved, an effort arises to keep its utilization high.

例如，假设一条单轨铁路穿过一个狭长的峡谷。^†为了提高单轨铁路的利用率，并增加客流量，人们可以在峡谷中途的宽阔处安装一个道岔和一条短侧轨，让火车同时双向行驶。然后，如果人们在调度方面小心谨慎，相反方向的火车就会在侧轨相遇，在那里它们可以互相通过，有效地使轨道每天可以承载的火车数量翻倍。然而，现在的火车运营比以前复杂得多。如果任何一列火车晚点，两列火车的时间表都会被打乱。需要安装信号系统，因为人类调度员或操作员可能会犯错误。而且——一个突发特性——火车现在的长度是有限制的。如果两列火车要在中间通过，至少有一列必须足够短，才能完全驶上侧轨。

Consider, for example, a single-track railroad line running through a long, narrow canyon.^† To improve the utilization of the single track, and push more traffic through, one might allow trains to run both ways at the same time by installing a switch and a short side track in a wide spot about halfway through the canyon. Then, if one is careful in scheduling, trains going in opposite directions will meet at the side track, where they can pass each other, effectively doubling the number of trains that the track can carry each day. However, the train operations are now much more complex than they used to be. If either train is delayed, the schedules of both are disrupted. A signaling system needs to be installed because human schedulers or operators may make mistakes. And—an emergent property—the trains now have a limit on their length. If two trains are to pass in the middle, at least one of them must be short enough to pull completely onto the side track.

峡谷中的火车很好地说明了提高利用率的努力如何增加复杂性。在努力提高利用率时，通常会遇到经济学家称之为的一般设计原则

The train in the canyon is a good illustration of how efforts to increase utilization can increase complexity. When striving for higher utilization, one usually encounters a general design principle that economists call

这种现象在试图更有效地利用资源时尤为明显：人们越是试图充分地利用稀缺资源，使用、分配和分布的策略就越复杂。因此，一个很少使用的街道交叉口不需要任何交通管制，只需要规定右边的汽车有优先通行权。随着使用量的增加，必须逐步应用更复杂的措施：停车标志，然后是交通信号灯，然后用多相灯标记转弯车道，然后是控制信号灯的车辆传感器。当进出机场的交通量接近机场的容量时，必须采取措施，例如堆放飞机、将飞机停在远处的机场地面上或协调几家航空公司的航班调度。一般来说，人们越是试图提高有限资源的利用率，复杂性就越大（见图1.2）。

This phenomenon is particularly noticeable in attempts to use resources more efficiently: the more completely one tries to use a scarce resource, the greater the complexity of the strategies for use, allocation, and distribution. Thus a rarely used street intersection requires no traffic control beyond a rule that the car on the right has the right-of-way. As usage increases, one must apply progressively more complex measures: stop signs, then traffic lights, then marked turning lanes with multiphase lights, then vehicle sensors to control the lights. As traffic in and out of an airport nears the airport’s capacity, measures such as stacking planes, holding them on the ground at distant airports, or coordinated scheduling among several airlines must be taken. As a general rule, the more one tries to increase utilization of a limited resource, the greater the complexity (see Figure 1.2).

图 1.2收益递减的一个例子：复杂性随着利用率的提高而增加。

Figure 1.2 An example of diminishing returns: complexity grows with increasing utilization.

敏锐的读者会注意到图 1.1和1.2是相同的。记住这个图很有用，因为它的某个版本可用于描述系统的许多不同方面。

The perceptive reader will notice that Figures 1.1 and 1.2 are identical. It would be useful to memorize this figure because some version of it can be used to describe many different things about systems.

1.3.1. 模块化

1.3.1. Modularity

降低复杂性的最简单、最重要的工具是分而治之技术：将系统分析或设计为一组相互作用的子系统，称为模块。这种技术的强大之处在于能够考虑模块内组件之间的相互作用，而无需同时考虑其他模块内的组件。

The simplest, most important tool for reducing complexity is the divide-and-conquer technique: analyze or design the system as a collection of interacting subsystems, called modules. The power of this technique lies primarily in being able to consider interactions among the components within a module without simultaneously thinking about the components that are inside other modules.

要了解减少交互的影响，请考虑调试一个包含N条语句的大型程序。假设程序中的错误数量与其大小成正比，并且错误随机分布在整个代码中。程序员编译程序、运行程序、发现错误、查找并修复错误，然后重新编译，然后再寻找下一个错误。还假设查找程序中的错误所需的时间大致与程序的大小成正比。然后我们可以对调试所花费的时间进行建模：

To see the impact of reducing interactions, consider the debugging of a large program with, say, N statements. Assume that the number of bugs in the program is proportional to its size and the bugs are randomly distributed throughout the code. The programmer compiles the program, runs it, notices a bug, finds and fixes the bug, and recompiles before looking for the next bug. Assume also that the time it takes to find a bug in a program is roughly proportional to the size of the program. We can then model the time spent debugging:

不幸的是，调试时间与程序大小的平方成正比。

Unfortunately, the debugging time grows proportional to the square of the program size.

现在假设程序员将程序分成K 个模块，每个模块的大小大致相等，因此每个模块包含N/K 个语句。如果模块实现独立功能，人们希望发现错误通常只需要检查一个模块。这样，调试任何一个模块所需的时间就以两种方式减少了：较小的模块可以更快地调试，而且由于较小的程序中的错误较少，任何一个模块都不需要调试那么多次。这两种影响被调试所有 K 个模块的需要部分抵消。因此，我们调试K 个模块系统所需时间的模型变为

Now suppose that the programmer divides the program into K modules, each of roughly equal size, so that each module contains N/K statements. To the extent that the modules implement independent features, one hopes that discovery of a bug usually will require examining only one module. The time required to debug any one module is thus reduced in two ways: the smaller module can be debugged faster, and since there are fewer bugs in smaller programs, any one module will not need to be debugged as many times. These two effects are partially offset by the need to debug all K modules. Thus our model of the time required to debug the system of K modules becomes

因此，模块化为K 个组件可将调试时间缩短K倍。尽管模块化减少工作量的具体机制因系统而异，但模块化的这一特性是通用的。因此，每个大型系统都具有模块化。

Modularization into K components thus reduces debugging time by a factor of K. Although the detailed mechanism by which modularity reduces effort differs from system to system, this property of modularity is universal. For this reason, one finds modularity in every large system.

我们在这里利用的模块化特点是，用改进的模块替换劣质模块很容易，从而允许逐步改进系统而无需完全重建系统。因此，模块化有助于控制由变化引起的复杂性。此功能不仅适用于调试，还适用于系统改进和演进的所有方面。同时，重要的是要认识到与模块化相关的设计原则，我们可以称之为

The feature of modularity that we are taking advantage of here is that it is easy to replace an inferior module with an improved one, thus allowing incremental improvement of a system without completely rebuilding it. Modularity thus helps control the complexity caused by change. This feature applies not only to debugging but to all aspects of system improvement and evolution. At the same time, it is important to recognize a design principle associated with modularity, which we may call

原因是，一旦某个接口已被其他模块使用，更改该接口至少需要替换两个模块。如果一个接口被许多模块使用，则更改该接口需要同时替换所有这些模块。因此，确保模块化的正确性尤为重要。

The reason is that once an interface has been used by another module, changing the interface requires replacing at least two modules. If an interface is used by many modules, changing it requires replacing all of those modules simultaneously. For this reason, it is particularly important to get the modularity right.

已经有整本书专门讲述模块化及其带来的好处。侧边栏 1.5介绍了其中一本书。

Whole books have been written about modularity and the good things it brings. Sidebar 1.5 describes one of those books.

1.3.2. 抽象

1.3.2. Abstraction

在模块化对调试时间的影响的数值示例中，一个重要的假设在实践中可能不成立：发现错误通常只会导致检查一个模块。要使该假设成立，还有一个要求：从一个模块到另一个模块的影响必须很少或没有传播。虽然有很多方法可以将系统划分为模块，但其中一些方法将被证明比其他方法更好——“根据自然形成，连接的位置，不要像一个糟糕的雕刻家那样破坏任何部分”（柏拉图，《斐德罗篇》265e，本杰明·乔伊特译本）。

An important assumption in the numerical example of the effect of modularity on debugging time may not hold up in practice: that discovery of a bug should usually lead to examining just one module. For that assumption to hold true, there is a further requirement: there must be little or no propagation of effects from one module to another. Although there are lots of ways of dividing a system up into modules, some of these ways will prove to be better than others—“according to the natural formation, where the joint is, not breaking any part as a bad carver might” (Plato, Phaedrus 265e, Benjamin Jowett translation).

因此，最好的划分通常遵循自然或有效的界限。它们的特点是模块之间的交互更少，并且从一个模块到另一个模块的影响传播更少。更一般地，它们的特点是任何模块能够完全根据其外部规范处理所有其他模块，而不需要了解内部发生的情况。对模块化的这种额外要求称为抽象。抽象是接口与内部、规范与实现的分离。由于抽象几乎总是伴随着模块化，所以有些作者并没有对这两个概念进行任何区分。有时，人们会看到功能模块化这个术语被用来表示具有抽象的模块化。

Thus the best divisions usually follow natural or effective boundaries. They are characterized by fewer interactions among modules and by less propagation of effects from one module to another. More generally, they are characterized by the ability of any module to treat all the others entirely on the basis of their external specifications, without need for knowledge about what goes on inside. This additional requirement on modularity is called abstraction. Abstraction is separation of interface from internals, of specification from implementation. Because abstraction nearly always accompanies modularity, some authors do not make any distinction between the two ideas. One sometimes sees the term functional modularity used to mean modularity with abstraction.

因此，人们购买 DVD 播放器时，会将其视为一个前面板上有十几个按钮的设备，并希望永远不要查看其内部。如果人们必须了解电视机内部设计的细节才能选择兼容的 DVD 播放器，那么没有人会购买该播放器。同样，人们将包裹交给隔夜快递服务，而不需要了解该服务将使用的具体车辆类型或路线。唯一需要担心的是包裹明天会送到。

Thus one purchases a DVD player planning to view it as a device with a dozen or so buttons on the front panel and hoping never to look inside. If one had to know the details of the internal design of a television set in order to choose a compatible DVD player, no one would ever buy the player. Similarly, one turns a package over to an overnight delivery service without feeling a need to know anything about the particular kinds of vehicles or routes the service will use. Confidence that the package will be delivered tomorrow is the only concern.

在计算机世界中，抽象以无数种方式出现。顺序电路记住状态的一般能力被抽象为特定的、易于描述的模块，称为寄存器。程序被设计为隐藏其复杂数据结构表示的细节以及它们调用的其他程序的细节。用户期望易于使用、按钮式的应用程序界面（如计算机游戏、电子表格程序或 Web 浏览器）能够抽象出内存、处理器、通信和显示管理等极其复杂的基础。

In the computer world, abstraction appears in countless ways. The general ability of sequential circuits to remember state is abstracted into particular, easy-to-describe modules called registers. Programs are designed to hide details of their representation of complex data structures and details of which other programs they call. Users expect easy-to-use, button-pushing application interfaces such as computer games, spreadsheet programs, or Web browsers that abstract incredibly complex underpinnings of memory, processor, communication, and display management.

如果由于实现错误而导致无意或意外的互连，甚至出于善意的设计试图越过模块边界以提高性能或满足其他要求，则最小化模块间互连的目标可能会失败。软件特别容易受到此问题的影响，因为单独编译的子程序提供的模块边界有些软，并且很容易被使用指针、填充缓冲区或计算数组索引时的错误所穿透。因此，系统设计人员更喜欢通过在模块之间插入坚不可摧的墙壁来强制模块化的技术。这些技术确保不会出现无意或隐藏的互连。第4 章和第 5 章介绍了一些用于强制模块化的技术。

The goal of minimizing interconnections among modules may be defeated if unintentional or accidental interconnections occur as a result of implementation errors or even well-meaning design attempts to sneak past modular boundaries in order to improve performance or meet some other requirement. Software is particularly subject to this problem because the modular boundaries provided by separately compiled subprograms are somewhat soft and easily penetrated by errors in using pointers, filling buffers, or calculating array indices. For this reason, system designers prefer techniques that enforce modularity by interposing impenetrable walls between modules. These techniques ensure that there can be no unintentional or hidden interconnections. Chapters 4 and 5 develop some of these techniques for enforcing modularity.

设计良好且正确执行的模块化抽象对于限制故障的影响尤其重要，因为它们可以控制影响的传播。正如我们在第 8 章 [在线] 中学习容错时所看到的那样，模块是故障遏制的单位，故障的定义是模块不符合其抽象接口规范。

Well-designed and properly enforced modular abstractions are especially important in limiting the impact of faults because they control propagation of effects. As we shall see when we study fault tolerance in Chapter 8 [on-line], modules are the units of fault containment, and the definition of a failure is that a module does not meet its abstract interface specifications.

与抽象密切相关的是使模块化在实践中发挥作用的重要设计规则：

Closely related to abstraction is an important design rule that makes modularity work in practice:

这一原则意味着，模块在设计时应尽量自由地解释其输入值，即使输入值不在指定范围内，只要能够合理地解释它们，就应接受它们。另一方面，模块应根据其规范保守地构建其输出 — 如果可能的话，使其输出比规范要求的更准确或更受约束。稳健性原则的效果是倾向于抑制而不是传播甚至放大模块间接口中出现的噪声或错误。

This principle means that a module should be designed to be liberal in its interpretation of its input values, accepting them even if they are not within specified ranges, if it is still apparent how to sensibly interpret them. On the other hand, the module should construct its outputs conservatively in accordance with its specification—if possible making them even more accurate or more constrained than the specification requires. The effect of the robustness principle is to tend to suppress, rather than propagate or even amplify, noise or errors that show up in the interfaces between modules.

稳健性原则是现代大规模生产的核心思想之一。从历史上看，机械师制造需要配合的部件时，首先加工一个部件，然后再加工第二个部件，使其与第一个部件精确贴合，这种技术称为配合。这一突破源于人们的认识：如果指定了部件的公差，并将每个部件设计为与任何在其指定公差范围内的其他部件配合，那么就有可能通过使用可互换零件来实现模块化并加快制造速度。显然，这一概念首次成功应用于 1822 年的一份向美国陆军交付步枪的合同。在 T 型车生产线创建时，亨利·福特用这句格言概括了这一概念：“大规模生产中没有装配工。”

The robustness principle is one of the key ideas underlying modern mass production. Historically, machinists made components that were intended to mate by machining one of the components and then machining a second component to exactly fit against or into the first one, a technique known as fitting. The breakthrough came with the realization that if one specified tolerances for components and designed each component to mate with any other component that was within its specified tolerance, then it would be possible to modularize and speed up manufacturing by having interchangeable parts. Apparently, this concept was first successfully applied in an 1822 contract to deliver rifles to the United States Army. By the time production lines for the Model T automobile were created, Henry Ford captured the concept in the aphorism, “In mass production there are no fitters.”

稳健性原则在计算机系统中发挥着重要作用。它在人机界面、网络协议和容错方面尤其重要，并且正如本章1.4 节所解释的那样，它构成了数字逻辑的基础。同时，稳健性原则与另一个重要的设计原则之间存在着矛盾：

The robustness principle plays a major role in computer systems. It is particularly important in human interfaces, network protocols, and fault tolerance, and, as Section 1.4 of this chapter explains, it forms the basis for digital logic. At the same time, a tension exists between the robustness principle and another important design principle:

当输入不接近其指定值时，通常表明某些事情开始出错。越早发现问题，就能越早修复。因此，跟踪和报告超出容差范围的输入非常重要，即使稳健性原则允许成功解释这些输入。

When inputs are not close to their specified values, that is usually an indication that something is starting to go wrong. The sooner that something going wrong can be noticed, the sooner it can be fixed. For this reason, it is important to track and report out-of-tolerance inputs, even if the robustness principle would allow them to be interpreted successfully.

一些系统通过提供两种操作模式来实现安全边际原则，这两种模式可以称为“震荡”和“生产”。在震荡模式下，模块会仔细检查每个输入，并拒绝接受任何稍微超出规格的内容，从而可以立即发现问题和接近源头的编程错误。在生产模式下，模块会根据稳健性原则接受任何它们可以合理解释的输入。精心设计的系统将这两种想法融合在一起：接受任何合理的输入，但报告任何开始超出容差的输入，以便在完全无法使用之前对其进行修复。

Some systems implement the safety margin principle by providing two modes of operation, which might be called “shake-out” and “production”. In shake-out mode, modules check every input carefully and refuse to accept anything that is even slightly out of specification, thus allowing immediate discovery of problems and of programming errors near their source. In production mode, modules accept any input that they can reasonably interpret, in accordance with the robustness principle. Carefully designed systems blend the two ideas: accept any reasonable input but report any input that is beginning to drift out of tolerance so that it may be repaired before it becomes completely unusable.

1.3.3. 分层

1.3.3. Layering

使用良好抽象设计的系统往往会最大限度地减少其组件模块之间的互连数量。减少模块互连的一个有效方法是采用一种特殊的模块组织方法，称为分层。在使用分层设计时，人们以一组已经完成的机制（下层）为基础，并使用它们来创建另一组完整的机制（上层）。一个层本身可以实现为多个模块，但一般来说，给定层的模块只与同一层中的对等模块以及下一较高层和下一较低层的模块交互。这种限制可以显著减少大系统中潜在的模块间交互数量。

Systems that are designed using good abstractions tend to minimize the number of interconnections among their component modules. One powerful way to reduce module interconnections is to employ a particular method of module organization known as layering. In designing with layers, one builds on a set of mechanisms that is already complete (a lower layer) and uses them to create a different complete set of mechanisms (an upper layer). A layer may itself be implemented as several modules, but as a general rule, a module of a given layer interacts only with its peers in the same layer and with the modules of the next higher and next lower layers. That restriction can significantly reduce the number of potential intermodule interactions in a big system.

这种方法的一些最佳示例可以在计算机系统中找到：高级语言的解释器是使用较低级、更面向机器的语言实现的。尽管高级语言不允许表达任何新程序，但它更易于使用，至少对于它设计的应用程序而言。

Some of the best examples of this approach are found in computer systems: an interpreter for a high-level language is implemented using a lower-level, more machine-oriented, language. Although the higher-level language doesn’t allow any new programs to be expressed, it is easier to use, at least for the application for which it was designed.

因此，几乎每个计算机系统都包含多个层。最底层由门和存储单元组成，在此层之上构建了由处理器和内存组成的层。在此层之上构建了一个操作系统层，它充当处理器和内存层的增强。最后，应用程序在此增强的处理器和内存层上执行。在每一层中，下一层提供的功能都会根据上一层的方便进行重新排列、重新打包、重新抽象和重新解释。如第 7 章 [在线] 中所述，层也是数据通信网络的主要组织技术。

Thus, nearly every computer system comprises several layers. The lowest layer consists of gates and memory cells, upon which is built a layer consisting of a processor and memory. On top of this layer is built an operating system layer, which acts as an augmentation of the processor and memory layer. Finally, an application program executes on this augmented processor and memory layer. In each layer, the functions provided by the layer below are rearranged, repackaged, reabstracted, and reinterpreted as appropriate for the convenience of the layer above. As will be seen in Chapter 7 [on-line], layers are also the primary organizing technique of data communication networks.

分层设计并非计算机系统和通信所独有。房子的内部结构层由立柱、托梁和椽子组成，以提供形状和强度；一层护套和石膏板以防风；一层墙板、地板和屋顶瓦片以防水；还有一层装饰性油漆以使其美观。许多数学，特别是代数，都是以优雅的层次结构组织的（就代数而言，是整数、有理数、复数、多项式和具有多项式系数的多项式），这种组织结构是深入理解的关键。

Layered design is not unique to computer systems and communications. A house has an inner structural layer of studs, joists, and rafters to provide shape and strength, a layer of sheathing and drywall to keep the wind out, a layer of siding, flooring and roof tiles to make it watertight, and a cosmetic layer of paint to make it look good. Much of mathematics, particularly algebra, is elegantly organized in layers (in the case of algebra, integers, rationals, complex numbers, polynomials, and polynomials with polynomial coefficients), and that organization provides a key to deep understanding.

1.3.4. 层次结构

1.3.4. Hierarchy

应对复杂性的最后一种主要技术也是减少模块之间的互连，但是采用一种不同的、专门的方法。从一小组模块开始，将它们组装成一个稳定、自足且具有明确定义接口的子系统。接下来，组装一小组子系统以生成更大的子系统。这个过程一直持续，直到由少量相对较大的子系统构建出最终系统。结果是一个树状结构，称为层次结构。大型组织（例如公司）几乎总是以这种方式建立，一个经理只负责 5 到 10 名员工，更高级别的经理负责 5 到 10 名经理，一直到公司总裁，他可能要监督 5 到 10 名副总裁。同样的思路也适用于军队。即使是层也可以被认为是一种退化的一维层次结构。

The final major technique for coping with complexity also reduces interconnections among modules but in a different, specialized way. Start with a small group of modules, and assemble them into a stable, self-contained subsystem that has a well-defined interface. Next, assemble a small group of subsystems to produce a larger subsystem. This process continues until the final system has been constructed from a small number of relatively large subsystems. The result is a tree-like structure known as a hierarchy. Large organizations such as corporations are nearly always set up this way, with a manager responsible for only five to ten employees, a higher-level manager responsible for five to ten managers, on up to the president of the company, who may supervise five to ten vice presidents. The same thinking applies to armies. Even layers can be thought of as a kind of degenerate one-dimensional hierarchy.

层次结构还有很多其他引人注目的例子，从微观生物系统到亚历山大帝国的集结。赫伯特·西蒙的经典论文《复杂性的架构》[进一步阅读建议 1.4.3 ] 包含了大量此类例子，并提出了令人信服的论据，即在进化过程中，层次结构设计有更好的生存机会。原因是层次结构通过只允许子系统组件之间的交互来限制交互。层次结构限制了一个由N 个组件组成的系统，在最坏的情况下可能会出现N × ( N - 1) 个交互，因此每个组件只能与其自己子系统的成员交互，除了接口组件，该组件还与下一个更高层次的子系统的其他成员交互。（公司中的接口组件称为“经理”；军队中称为“指挥官”；程序中称为“应用程序编程接口”。）如果子系统的组件数量限制为 10 个，则无论系统规模如何增长，这个数字都保持不变。最低级别子系统有N /10 个，下一个更高级别子系统有N /100 个，依此类推，但子系统总数以及交互次数仍与N成比例。与模块化减少调试工作量的方式类似，层次结构将模块间潜在交互的数量从平方律减少到线性。

There are many other striking examples of hierarchy, ranging from microscopic biological systems to the assembly of Alexander’s empire. A classic paper by Herbert Simon, “The architecture of complexity” [Suggestions for Further Reading 1.4.3], contains an amazing range of such examples and offers compelling arguments that, under evolution, hierarchical designs have a better chance of survival. The reason is that hierarchy constrains interactions by permitting them only among the components of a subsystem. Hierarchy constrains a system of N components, which in the worst case might exhibit N × (N − 1) interactions, so that each component can interact only with members of its own subsystem, except for an interface component that also interacts with other members of the subsystem at the next higher level of hierarchy. (The interface component in a corporation is called a “manager” in an army it is called the “commanding officer” for a program it is called the “application programming interface”.) If subsystems have a limit of, say, 10 components, this number remains constant no matter how large the system grows. There will be N/10 lowest level subsystems, N/100 next higher level subsystems, and so on, but the total number of subsystems, and thus the number of interactions, remains proportional to N. Analogous to the way that modularity reduces the effort of debugging, hierarchy reduces the number of potential interactions among modules from square-law to linear.

单个模块的设计者最能感受到这种影响。如果没有限制，原则上每个模块都应准备好与系统的其他每个模块进行交互。层次结构的优点是模块设计者可以只关注与其直接子系统的其他成员的接口的交互。

This effect is most strongly noticed by the designer of an individual module. If there are no constraints, each module should in principle be prepared to interact with every other module of the system. The advantage of a hierarchy is that the module designer can focus just on interactions with the interfaces of other members of its immediate subsystem.

1.3.5. 归纳起来：名字带来联系

1.3.5. Putting it Back Together: Names Make Connections

应对复杂性的四种技术——模块化、抽象化、分层和层次结构——提供了划分事物并将结果模块以适当的关系放置的方法。但是，我们仍然需要一种连接这些模块的方法。在数字系统中，主要的连接方法是让一个模块命名它打算使用的另一个模块。名称允许推迟决策、轻松地用更好的模块替换一个模块以及共享模块。软件以明显的方式使用名称。不太明显的是，连接到总线的硬件模块也使用名称进行互连——地址（包括总线地址）是一种名称。

The four techniques for coping with complexity—modularity, abstraction, layering, and hierarchy—provide ways of dividing things up and placing the resulting modules in suitable relation one to another. However, we still need a way of connecting those modules. In digital systems, the primary connection method is that one module names another module that it intends to use. Names allow postponing of decisions, easy replacement of one module with a better one, and sharing of modules. Software uses names in an obvious way. Less obviously, hardware modules connected to a bus also use names for interconnection—addresses, including bus addresses, are a kind of name.

在模块化系统中，通常可以找到多种方法来组合模块以实现所需的功能。设计人员必须在某个时候从众多可用实现中选择一种特定的实现。做出这种选择称为绑定。回想一下，模块化的强大之处在于能够用更好的实现替换一种实现，设计人员通常会尝试通过将绑定延迟到最后可能的时刻，甚至延迟到实际需要该功能的第一个时刻，来保持最大的灵活性。

In a modular system, one can usually find several ways to combine modules to implement a desired feature. The designer must at some point choose a specific implementation from among many that are available. Making this choice is called binding. Recalling that the power of modularity comes from the ability to replace an implementation with a better one, the designer usually tries to maintain maximum flexibility by delaying binding until the last possible instant, perhaps even until the first instant that the feature is actually needed.

延迟绑定的一种方法是只命名功能而不是实现它。使用名称允许人们将模块设计为好像另一个模块的功能存在一样，即使该功能尚未实现，并且它还使得以后选择不同的实现变得非常容易。当实际调用该功能时，名称当然必须绑定到另一个模块的实际实现。使用名称来延迟或允许更改绑定称为间接，它是设计原则的基础：

One way to delay binding is just to name a feature rather than implementing it. Using a name allows one to design a module as if a feature of another module exists, even if that feature has not yet been implemented, and it also makes it mechanically easy to later choose a different implementation. By the time the feature is actually invoked, the name must, of course, be bound to a real implementation of the other module. Using a name to delay or allow changing a binding is called indirection, and it is the basis of a design principle:

剑桥大学计算机科学家戴维·惠勒 (David Wheeler) 提出了这一原则的民间智慧版本，他夸大了间接层的力量，认为“计算机系统中的任何问题都可以通过增加一个间接层来解决”。这一民间智慧的一个更合理的版本是，任何计算机系统都可以通过删除一个间接层来提高速度。

A folk wisdom version of this principle, attributed to computer scientist David Wheeler of the University of Cambridge, exaggerates the power of indirection by suggesting that “any problem in a computer system can be solved by adding a layer of indirection.” A somewhat more plausible counterpart of this folk wisdom is the observation that any computer system can be made faster by removing a layer of indirection.

当一个模块有名称时，其他几个模块可以通过名称使用它，从而共享第一个模块中包含的设计工作、成本或信息。由于名称是数字系统中模块化的基石元素，因此第 2 章和第3章主要介绍命名方案的设计。

When a module has a name, several other modules can make use of it by name, thereby sharing the design effort, cost, or information contained in the first module. Because names are a cornerstone element of modularity in digital systems, Chapters 2 and 3 are largely about the design of naming schemes.

1.4.1. 计算机系统在组合上没有近似的界限

1.4.1. Computer Systems have no Nearby Bounds on Composition

计算机系统大多是数字化的，由软件控制。这两个特性分别导致其他系统中物理定律对复杂性的限制放宽。

Computer systems are mostly digital, and they are controlled by software. Each of these two properties separately leads to relaxations of what, in other systems, would be limits on complexity arising from physical laws.

首先考虑模拟系统和数字系统之间的差异。所有模拟系统都存在工程限制，即系统的每个组件都会产生噪声。这种噪声可能来自环境，例如振动或电磁辐射。噪声也可能出现，因为组件的物理行为并不严格遵循任何可处理的运行模型：土木工程师指定放在桥台下的一堆岩石不遵循简单的变形模型；电子电路中的电阻器会产生随机噪声，其水平取决于温度。当模拟组件组成系统时，来自各个组件的噪声会累积（如果噪声源在统计上独立，噪声可能只会缓慢累积，但仍然会累积）。随着组件数量的增加，噪声将在某个时候主导系统的行为。（此分析适用于人类工程师设计的系统。自然生物、热力学和宏观经济系统由数十亿个模拟组件组成，它们以某种方式使用层次结构、分层、抽象和模块化来运行，尽管存在噪声，但它们非常复杂，我们对它们的了解还不足以采用相同的技术。）

Consider first the difference between analog and digital systems. All analog systems have the engineering limitation that each component of the system contributes noise. This noise may come from the environment in the form of, for example, vibration or electromagnetic radiation. Noise may also appear because the component’s physical behavior does not precisely follow any tractable model of operation: the pile of rocks that a civil engineer specifies to go under a bridge abutment does not obey a simple deformation model; a resistor in an electronic circuit generates random noise whose level depends on the temperature. When analog components are composed into systems, the noise from individual components accumulates (if the noise sources are statistically independent, the noise may accumulate only slowly but it still accumulates). As the number of components increases, noise will at some point dominate the behavior of the system. (This analysis applies to systems designed by human engineers. Natural biological, thermodynamic, and macroeconomic systems, composed of billions of analog components, somehow use hierarchy, layering, abstraction, and modularity to operate despite noise, but they are so complex that we do not understand them well enough to adopt the same techniques.)

因此，噪声限制了设计师可以有效组合的模拟元件数量，或设计师可以有效级联的级数。这一论点适用于任何工程模拟系统：横跨河流的桥梁、立体声音响或客机。这就是复印件比原件更难读取的原因。尺寸上可能还有其他限制（例如，由于材料强度），但噪声始终是模拟系统复杂性的限制。

Noise thus provides a limit on the number of analog components that a designer can usefully compose or on the number of stages that a designer can usefully cascade. This argument applies to any engineered analog system: a bridge across a river, a stereo, or an airliner. It is the reason a photocopy of a photocopy is harder to read than the original. There may also be other limits on size (arising from the strength of materials, for example), but noise is always a limit on the complexity of analog systems.

相比之下，数字系统没有噪声；因此复杂性可以增长，而不受噪声限制。数字逻辑设计人员使用一种称为静态原则的稳健性原则。这种原则是数字系统魔力的主要来源。静态原则要求设备接受的数字值ONE（或ZERO）的模拟值范围要比设备输出的数字值 ONE（或 ZERO ）的模拟值范围更宽。这种原则是对输入宽容、对输出严格的一个例子。

In contrast, digital systems are noise-free; complexity can therefore grow without any constraint of a bound arising from noise. The designers of digital logic use a version of the robustness principle known as the static discipline. This discipline is the primary source of the magic that seems to surround digital systems. The static discipline requires that the range of analog values that a device accepts as meaning the digital value ONE (or ZERO) be wider than the range of analog values that the device puts out when it means digital ONE (or ZERO). This discipline is an example of being tolerant of inputs and strict on outputs.

数字系统在较低层次上由模拟组件构成。为此目的而选择的模拟组件是非线性的，它们在输入和输出之间具有增益。如果使用得当，非线性可使输入具有较大的公差，而增益可确保输出保持在较窄的规格范围内，如图1.3所示。它们共同产生了数字电路的称为电平恢复或再生的属性。再生信号电平会出现在每个数字组件的输出端，无论它们的粒度级别如何：门、触发器、存储芯片、处理器或完整的计算机系统。再生电平可创建清晰的接口，让一个子系统可以放心地连接到下一个子系统。与土木工程师的一堆石头不同，逻辑门的性能完全符合设计者的意图。

Digital systems are, at some lower level, constructed of analog components. The analog components chosen for this purpose are non-linear, and they have gain between input and output. When used appropriately, non-linearity allows inputs to have a wide tolerance, and gain ensures that outputs stay within narrow specifications, as shown in Figure 1.3. Together they produce the property of digital circuits called level restoration or regeneration. Regenerated signal levels appear at the output of every digital component, whatever their level of granularity: a gate, a flip-flop, a memory chip, a processor, or a complete computer system. Regenerated levels create clean interfaces that allow one subsystem to be connected to the next with confidence. Unlike the civil engineer’s pile of rocks, a logic gate performs exactly as its designer intends.

图 1.3数字元件的增益和非线性如何恢复电平。输入电平和输出电平跨越相同的值范围，但可接受的输入范围比生成的输出范围宽得多。

Figure 1.3 How gain and non-linearity of a digital component restore levels. The input level and output level span the same range of values, but the range of accepted inputs is much wider than the range of generated outputs.

静态规则和电平恢复不能保证具有数字输入和输出的设备永远不会出错。任何组件都可能出现故障。或者，本来应该为ONE的输入信号可能远远超出容差范围，以至于接收组件将其接受为ZERO。当发生这种情况时，错误接受该值的组件的输出也可能是错误的。重要的后果是数字组件会犯大错误，而不是小错误，正如我们在容错章节中看到的那样，大错误相对容易检测和处理。

The static discipline and level restoration do not guarantee that devices with digital inputs and outputs never make mistakes. Any component can fail. Or an input signal that is intended to be a ONE may be so far out of tolerance that the receiving component accepts it as a ZERO. When that happens, the output of the component that accepted that value incorrectly is likely to be wrong, too. The important consequence is that digital components make big mistakes, not little ones, and as we shall see when we reach the chapter on fault tolerance, big mistakes are relatively easy to detect and handle.

如果信号在通过一系列设备时不会积累噪声，那么噪声就不会限制可以串联的设备数量。换句话说，噪声不会限制数字系统的最大构图深度。与模拟系统不同，数字系统的复杂性可以不断增加，直到超出设计人员的理解能力。截至 2009 年，处理器芯片包含超过 20 亿个晶体管，远远超过任何模拟芯片。没有哪架客机拥有如此多的组件——除了机载计算机。

If a signal does not accumulate noise as it goes through a string of devices, then noise does not limit the number of devices one can string together. In other words, noise does not constrain the maximum depth of composition for digital systems. Unlike analog systems, digital systems can grow in complexity until they exceed the ability of their designers to understand them. As of 2009, processor chips contain over two billion transistors, far more than any analog chip. No airliner has nearly that many components—except in its on-board computers.

组合没有短期界限的第二个原因是计算机系统是由软件控制的。静态规则对复杂性的贡献可能很糟糕，但软件的贡献却更糟糕。硬件至少受到一些物理限制——光速、实际半导体材料中信号的稳定速率、相邻组件之间不必要的电耦合、热量的去除速率以及占用的空间。软件似乎没有任何物理限制，除了可用的内存来存储它和处理器来执行它。因此，软件的组合可以像人们创建它一样快。因此，我们经常听说操作系统、数据库系统甚至文字处理器由超过 1000 万个程序语句组成。

The second reason composition has no nearby bounds is that computer systems are controlled by software. Bad as the contribution to complexity from the static discipline may be, the contribution from software turns out to be worse. Hardware is at least subject to some physical limits—the speed of light, the rate of settling of signals in real semiconductor materials, unwanted electrical coupling between adjacent components, the rate at which heat can be removed, and the space that it occupies. Software appears to have no physical limits whatever beyond the availability of memory to store it and processors to execute it. As a result, composition of software can go on as fast as people can create it. Thus one routinely hears of operating systems, database systems, and even word processors consisting of more than 10 million program statements.

原则上，抽象可以通过将实现隐藏在模块接口之下来帮助控制软件组合。问题是，大多数抽象实际上都存在轻微的“漏洞”，因为它们无法完美地隐藏底层实现。漏洞的一个简单示例是整数加法：在大多数实现中，只要结果适合可用的字长，加法运算就完全符合数学规范，但如果结果大于该字长，则产生的溢出会给程序员带来麻烦。漏洞就像模拟系统中的噪声一样，会随着软件模块数量的增加而累积。与噪声不同，它以复杂性的形式累积，因此软件组合缺乏物理约束仍然是一个根本问题。因此，从机械角度来看，创建一个复杂性远远超出其设计者理解能力的系统是很容易的。而且由于这很容易，所以它经常发生，有时还会带来灾难性的后果。^*

In principle, abstraction can help control software composition by hiding implementation beneath module interfaces. The problem is that most abstractions are, in reality, slightly “leaky” in that they don’t perfectly conceal the underlying implementation. A simple example of leakiness is addition of integers: in most implementations, the addition operation perfectly matches the mathematical specification as long as the result fits in the available word size, but if the result is larger than that, the resulting overflow becomes a complication for the programmer. Leakiness, like noise in analog systems, accumulates as the number of software modules grows. Unlike noise, it accumulates in the form of complexity, so the lack of physical constraints on software composition remains a fundamental problem. It is, therefore, mechanically easy to create a system with complexity that is far beyond the ability of its designers to understand. And since it is easy, it happens often, and sometimes with disastrous results.^*

由于数字硬件的组成没有噪声限制，而软件的组成又有非常遥远的物理限制，粗心的设计师很容易滥用模块化、抽象、分层和层次结构等工具来增加复杂性。这种现象在桥梁和客机的设计中是鲜为人知的。与其他系统相比，计算机系统允许组合达到一定的深度，而设计师的理解能力是其首要限制。不幸的是，由于缺乏对组合深度的自然物理限制，设计师不得不构建更复杂的系统。如果自然没有对组合施加一个近似的限制，设计师就必须自己施加一个限制。由于很难拒绝一个听起来合理的功能，因此功能不断被添加。这就是太多计算机系统设计的命运。

Between the absence of a noise-imposed limit on composition of digital hardware and very distant physical limits on composition of software, it is too easy for an unwary designer to misuse the tools of modularity, abstraction, layering, and hierarchy to include still more complexity. This phenomenon is quite unknown in the design of bridges and airliners. In contrast with other systems, computer systems allow composition to a depth whose first limit is the designer’s ability to understand. Unfortunately, this lack of nearby natural, physical bounds on depth of composition tempts designers to build more complex systems. If nature does not impose a nearby limit on composition, the designer must self-impose a limit. Since it can be hard to say no to a reasonable-sounding feature, features keep getting added. Therein lies the fate of too many computer system designs.

1.4.2. d(技术)/dt 是前所未有的

1.4.2. d(technology)/dt is Unprecedented

出于边栏 1.6中部分解释的原因，在过去 35 年中，用于计算和通信的数字硬件的成本每年平均下降约 30%。这种变化速度意味着仅仅两年的时间就足以让技术将价格降低一半，而在七八年内，它就导致价格下降了 10 倍。一些组件的改进速度甚至更快。图 1.4显示了 25 年间磁盘存储的成本。在此期间，磁盘价格实际上大约每五年下降 10 倍，因此磁盘价格每年下降近 60%。磁盘专家预测至少在未来几年内仍将保持类似的改进速度。他们的预测似乎相对安全，因为已经致力于下一轮磁记录技术的开发实验室没有报告任何重大障碍。类似的图表适用于随机存取存储器、处理器成本和光纤传输速度。

For reasons partly explained by Sidebar 1.6, during the last 35 years the cost of the digital hardware used for computation and communication has dropped an average of about 30% each year. This rate of change means that just two years’ passage of time has been enough to allow technology to cut prices in half, and in seven or eight years it has led to a drop in prices by a factor of 10. Some components have experienced even greater rates of improvement. Figure 1.4 shows the cost of magnetic disk storage over a 25-year span. During that time, disk prices have actually dropped by a factor of 10 roughly every five years, so disk prices have dropped nearly 60% each year. Disk experts project a similar rate of improvement for at least another few years. Their projection seems relatively safe, since no major roadblocks have been reported by development laboratories that are already working on the next rounds of magnetic recording technology. Similar charts apply to random access memory, processor cost, and the speed of optical fiber transmission.

图 1.4 1983 年至 2007 年磁盘价格历史及预测。

Figure 1.4 Magnetic disk price history and projection, 1983–2007.

技术的快速变化造成了计算机系统与其他工程系统之间的巨大差异。由于复杂系统的构建可能需要数年时间，因此当计算机系统准备交付时，其最初设计的基本规则已经发生了变化。不相称的缩放通常意味着当任何系统参数改变 2 倍时，设计人员必须调整应变，因为并非所有组件都按相同比例放大（或缩小）。更重要的是，当任何系统参数改变（十进制）数量级时，通常需要全新的设计。关于参数变化引起的应变的经验法则为我们提供了下一个设计原则：

This rapid change of technology has created a substantial difference between computer systems and other engineering systems. Since complex systems can take several years to build, by the time a computer system is ready for delivery, the ground rules under which it was originally designed have shifted. Incommensurate scaling typically means that the designer must adjust for strains when any system parameter changes by a factor of 2, because not all of the components scale up (or down) by the same proportion. More to the point, a whole new design is usually needed when any system parameter changes by a (decimal) order of magnitude. This rule of thumb about strains caused by parameter changes gives us our next design principle:

这条规则与观察到的技术变化率相结合，意味着当新设计的计算机系统准备交付时，它可能已经需要两轮调整，并准备进行彻底的重新设计。即使设计师试图预测技术变化的影响，水晶球充其量也只是模糊的。更糟糕的是，在系统开发过程中，运行速度可能比系统完成时慢一个数量级，代码和数据不适合可用的地址空间，或者数据必须分布在多个硬盘上，而不是很好地放在一个硬盘上。人们可以弥补这些问题中的每一个，但每一种这样的补偿都会消耗智力资源并增加开发过程的复杂性。

This rule, when combined with the observed rate of change of technology, means that by the time a newly designed computer system is ready for delivery it may have already needed two rounds of adjustment and be ready for a complete redesign. Even if the designer has tried to predict the impact of technology change, crystal balls are at best cloudy. Worse, during the development of the system, things may run an order of magnitude slower than they will when the system is finished, the code and data don’t fit in the available address space, or perhaps the data has to be partitioned across several hard disks instead of nicely fitting on one. One can compensate for each of these problems, but each such compensation absorbs intellectual resources and contributes complexity to the development process.

即使没有这些调整或重新设计，最初的计划可能已经是一种新设计。一座桥梁（或飞机）可能与之前的桥梁（或飞机）有少量不同，但土木工程师（或航空工程师）最终设计的东西几乎总是与之前的桥梁（或飞机）只有一点点不同。在计算机系统的情况下，一两年前完全不切实际的想法很快就会成为主流，因此计算机系统设计师最终设计的东西几乎总是与之前的计算机系统有显著不同。这种差异使得对先前设计的深入分析对土木工程师和航空工程师来说比对计算机系统设计师更有价值，并且通常意味着在计算机系统中，在进行下一次重大修订之前，没有时间发现和解决先前设计的大部分错误。这些错误会大大增加复杂性。

Even without those adjustments or redesign, the original plan was probably already a new design. A bridge (or airplane) may have a modest number of things that are different from the previous one, but a civil (or aeronautical) engineer almost always ends up designing something that is only a little different from some previous bridge (or airplane). In the case of computer systems, ideas that were completely unrealistic a year or two ago can become mainstream in no time, so the computer system designer almost always ends up designing something that is significantly different from the previous computer system. This difference makes deep analysis of previous designs more rewarding for civil and aeronautical engineers than for computer system designers, and also usually means that in computer systems there hasn’t been time to discover and iron out most of the mistakes of the previous design before going on to the next major revision. Those mistakes can contribute strongly to complexity.

由于技术进步如此之快，计算机系统设计领域往往不像其他大多数工程领域那样重视详细的性能分析和微调。如果一台新的蒸汽涡轮机能将能量传输提高 1%，那么发电系统可能会从中受益匪浅，而计算机系统所需的 20% 性能改进通常只需等待四个月的下一轮硬件产品发布即可实现。如果重写应用程序以获得同样的改进需要一年的工作量，那么等待技术变革来解决问题可能更具成本效益。换句话说，技术的快速进步意味着蛮力解决方案（购买更多内存、等待更快的处理器、使用更简单的算法）通常是正确的方法，而在其他系统中，它们可能是不可想象的。穿越峡谷的铁路的所有者可能不会认为将峡谷炸宽并安装第二条轨道的提议在经济上是合理的。即使有资源可用，对环境的影响也会成为阻碍。

Because technology has improved so rapidly, the field of computer system design tends to place much less emphasis on detailed performance analysis and fine-tuning than do most other engineering endeavors. Where an electric power generation system may benefit dramatically from a new steam turbine that improves energy transfer by 1%, a needed 20% improvement in performance of a computer system can usually be obtained just by waiting four months for the next round of hardware product announcements. If a proposal to rewrite an application to obtain that same improvement would require a year of work, it is probably more cost-effective to just wait for technology change to solve the problem. Put another way, rapidly improving technology means that brute-force solutions (buy more memory, wait for a faster processor, use a simpler algorithm) are often the right approach in computer systems, whereas in other systems they may be unthinkable. The owner of the railroad through the canyon probably would not view as economically reasonable a proposal to blast the canyon wider and install a second track. Even if the resources were available, the environmental impact would be a deterrent.

计算机系统技术快速变化的第二个主要后果是，计算机系统的可用性以及与“人机工程”相关的品质总是参差不齐。要使系统变得可用、友好和宽容需要多年的反复试验，但当计算机技术的一个层次被掌握后，计算机技术的新层次就有可能以相同的成本提供许多新功能，或者以更便宜的价格向大量没有准备的新用户提供以前的功能。

A second major consequence of the rapid rate of change of technology in computer systems is that usability, and related qualities that go under the label “human engineering”, of computer systems is always ragged. It takes years of trial and error to make systems usable, friendly, and forgiving, but by the time one level of computer technology has been tamed, a new level of computer technology opens the possibilities of many new features at the same cost, or of providing the previous features more cheaply to a vast new audience of unprepared users.

同样，法律和司法程序需要几十年才能解决新问题，因为人们会争论各种政策的合理性、发现滥用行为并探索替代补救措施。面对快速变化的计算机系统技术，这些流程远远落后，延迟了如何奖励创新软件创意或应制定哪些规则保护计算机中存储的信息等问题的解决，并增加了计算机系统设计人员负担的需求不确定性。^*

Similarly, legal and judicial processes take decades to come to grips with new issues, as people debate the wisdom of various policies, discover abuses, and explore alternative remedies. In the face of rapidly changing computer system technology, these processes fall far behind, delaying resolution of such concerns as how to reward innovative software ideas, or what rules should protect information stored in computers, and adding uncertainty of requirements to the burden of the computer system designer.^*

最后，现代的高速通信技术覆盖全球，大大加快了人们发现新技术的实用性并加以采用的速度。电力和电话从新奇事物发展到广泛使用用了几十年的时间，而数码相机和 DVD 等最新发明在不到十年的时间内就席卷了市场，CNN 或《新闻周刊》上只要提到一个以前不为人知的万维网网站，该网站就会突然被每天数百万次的点击量所淹没。更普遍的是，新出现的可行应用程序（如点对点文件共享）几乎可以在一夜之间改变现有系统的工作负载状况。

Finally, modern high-speed communications with global reach have greatly accelerated the rate at which people discover that a new technology is useful and adopt it. Where it took several decades for electricity and the telephone to move from curiosities to widespread use, recent innovations such as digital cameras and DVDs have swept their markets in less than a decade, and a single mention of a previously obscure World Wide Web site on CNN or in Newsweek magazine can cause that site to be suddenly overwhelmed with millions of hits per day. More generally, newly viable applications, such as peer-to-peer file sharing, can change the shape of the workload on existing systems practically overnight.

因此，计算机系统研究涉及规划、检查需求、定制细节以及与用户和社会整合的常规过程的压缩。这种压缩导致交付的系统存在缺陷，没有最聪明的想法。建造飞机和桥梁的人不必面对这些问题。这些问题可以被视为令人沮丧的困难或令人兴奋的挑战，这取决于一个人的观点。

Thus, the study of computer systems involves telescoping of the usual processes of planning, examining requirements, tailoring details, and integrating with users and society. This telescoping leads to the delivery of systems that have rough edges and without the benefit of the cleverest thought. People who build airplanes and bridges do not have to face these problems. Such problems can be viewed either as a frustrating difficulty or as an exciting challenge, depending on one’s perspective.

1.5.1. 为什么模块化、抽象、分层和等级制度还不够

1.5.1. Why Modularity, Abstraction, Layering, and Hierarchy aren’t Enough

模块化、抽象、分层和层次结构有很大帮助，但它们本身不足以控制由此产生的复杂性。原因是这四种技术都假设设计师了解正在设计的系统。在现实的、快速变化的计算机系统世界中，很难做出选择

Modularity, abstraction, layering, and hierarchy are a major help, but by themselves they aren’t enough to keep the resulting complexity under control. The reason is that all four of those techniques assume that the designer understands the system being designed. In the real, fast-changing world of computer systems, it is hard to choose

虽然有一些设计原则可用，但它们太少了，唯一真正的指导来自于以前系统的经验。

Although some design principles are available, they are far too few, and the only real guidance comes from experience with previous systems.

正如所料，计算机系统的设计人员已经开发并改进了至少一种额外的技术来应对复杂性。其他类型系统的设计人员也使用这种技术，但他们通常不认为它对成功的重要性与对计算机系统的重要性一样高，可能是因为这种技术在软件方面特别可行。这是一个称为迭代的开发过程。

As might be expected, designers of computer systems have developed and refined at least one additional technique to cope with complexity. Designers of other kinds of systems use this technique as well, but they usually do not consider it to be so fundamental to success as it is for computer systems, probably because the technique is particularly feasible with software. It is a development process called iteration.

1.5.2. 迭代

1.5.2. Iteration

迭代的本质是先构建一个简单、可运行的系统，该系统仅满足一小部分需求，然后逐步改进该系统，以逐渐涵盖越来越多的全套需求。这个想法是，小步前进有助于降低复杂性压倒系统设计的风险。始终拥有一个可用的工作系统有助于确保可以构建某些东西，并提供当前技术基本规则的持续体验以及发现和修复错误的机会。最后，在系统开发过程中对技术变化的调整更容易作为一个或多个迭代的一部分纳入其中。当您看到一个被标识为“版本 5.4”的软件时，这通常表明供应商正在使用迭代。

The essence of iteration is to start by building a simple, working system that meets only a modest subset of the requirements and then evolve that system in small steps to gradually encompass more and more of the full set of requirements. The idea is that small steps can help reduce the risk that complexity will overwhelm a system design. Having a working system available at all times helps provide assurance that something can be built and provides on-going experience with the current technology ground rules as well as an opportunity to discover and fix bugs. Finally, adjustments for technology changes that arrive during the system development are easier to incorporate as part of one or more of the iterations. When you see a piece of software identified as “release 5.4”, that is usually an indication that the vendor is using iteration.

成功的迭代需要相当的远见。这种远见涉及几个要素，其中两个我们定义为设计原则：

Successful iteration requires considerable foresight. That foresight involves several elements, two of which we identify as design principles:

迭代听起来像是一种简单的技术，但它往往会受到一些障碍的干扰。主要的障碍是，随着设计通过一系列迭代不断发展，可能会出现失去概念完整性的风险。这种风险意味着，系统最初、最简单版本的总体规划必须适应达到最终版本所需的所有迭代（因此需要有远见）。必须有人时刻保持警惕，以确保尽管在迭代过程中进行了更改，但总体设计原理仍然清晰。

Iteration sounds like a straightforward technique, but several obstacles tend to interfere with it. The main obstacle is that as a design evolves through a series of iterations, a risk of losing conceptual integrity arises. That risk suggests that the overall plan for the initial, simplest version of the system must accommodate all of the iterations needed to reach the final version (thus the need for foresight). Someone must constantly be on guard to make sure that the overall design rationale remains clear despite changes made during iteration.

在大多数组织中，好消息（例如，系统的主要部分正在提前完成工作）会迅速传遍整个组织，但坏消息（例如，某个重要模块尚未工作）通常只限于发现该消息的组织部分，至少直到该部分能够解决问题并报告好消息为止。这种现象称为坏消息二极管，会阻碍人们认识到更改系统的其他部分更为合适。

In most organizations, good news (e.g., a major piece of the system is working ahead of schedule) flows rapidly throughout the organization, but bad news (e.g., an important module isn’t working yet) often gets confined to the part of the organization that discovers it, at least until it can fix the problem and report good news. This phenomenon, the bad-news diode, can prevent realization that changing a different part of the system is more appropriate.

一个相关的问题是，当有人最终意识到模块化是错误的，出于两个原因，很难改变。首先，不可动摇的基础规则（见第 20 页）开始发挥作用。根据定义，改变模块化涉及改变多个模块，有时甚至多个模块。其次，设计师投入时间和精力开发一个从他们的角度来看是按预期完成的模块，他们可能不愿意看到这些时间和精力在返工中白白浪费。简而言之，要改变模块化，必须处理已承诺的组件和已承诺的设计师。

A related problem is that when someone finally realizes that the modularity is wrong, it can be hard to change, for two reasons. First, the unyielding foundations rule (see page 20) comes into play. Changing modularity by definition involves changing more than one module, and sometimes several. Second, designers who have invested time and effort in developing a module that, from their point of view, is doing what was intended can be reluctant to see this time and effort lost in a rework. Simply put, to change modularity one must deal with both committed components and committed designers.

当初始设计既简单又成功时，迭代的长期风险有时会显现出来。成功可能会导致设计师过于自信，并在后续迭代中过于雄心勃勃。自部署系统初始版本以来，技术已经得到改进，反馈建议了许多新功能。每个建议的功能本身看起来都很简单，很难判断它们会如何相互作用。结果往往是灾难性的过度扩张和随之而来的失败，这种失败非常常见，以至于有一个名字：第二系统效应。

A longer-term risk of iteration sometimes shows up when the initial design is both simple and successful. Success can lead designers to be overconfident and to be too ambitious on a later iteration. Technology has improved in the time since deployment of the initial version of the system and feedback has suggested lots of new features. Each suggested feature looks straightforward by itself, and it is difficult to judge how they might interact. The result is often a disastrous overreaching and consequent failure that is so common that it has a name: the second-system effect.

迭代可以被认为是将模块化应用于系统设计和实施过程的管理。因此，它将我们带入了管理技术的领域，而本书并未直接涉及这些领域。^*

Iteration can be thought of as applying modularity to the management of the system design and implementation process. It thus takes us into the realm of management techniques, which are not directly addressed in this book.^*

1.5.3. 保持简单

1.5.3. Keep it Simple

值得注意的是，应对复杂性最有效的技术之一也是最难应用的技术：简单性。如第 1.4.1 节所述，计算机系统缺乏自然的物理限制来抑制其复杂性，因此设计师必须施加限制；否则设计师可能会不堪重负。

Remarkably, one of the most effective techniques in coping with complexity is also one that is most difficult to apply: simplicity. As Section 1.4.1 explained, computer systems lack natural physical limits to curb their complexity, so the designer must impose limits; otherwise the designer risks being overwhelmed.

显而易见的建议是保持简单，但问题在于

The problem with the apparently obvious advice to keep it simple is that

这些考虑使得我们很难对任何一项要求、功能、例外或复杂情况说“不”。正是它们的累积影响导致了图 1.1所示的复杂性爆炸式增长。系统设计师必须始终牢记这种累积影响。最重要的是，计算机系统设计师对抗复杂性的最有力武器就是说“不。这会让事情变得太复杂。”

These considerations make it hard to say “no” to any one requirement, feature, exception, or complication. It is their cumulative impact that produces the complexity explosion illustrated in Figure 1.1. The system designer must keep this cumulative impact in mind at all times. The bottom line is that a computer system designer’s most potent weapon against complexity is the ability to say, “No. This will make it too complicated.”

当我们继续研究特定的计算机系统工程主题时，我们将充分利用一种特殊的简单性，在某种程度上它是另一种设计原则：

As we proceed to study specific computer system engineering topics, we shall make much use of a particular kind of simplicity, to the extent that it is yet another design principle:

每个主题领域都会明确引入一个或多个全面的简化。原因是它们允许设计者提出令人信服的正确性论据，使细节变得无关紧要，并让所有参与者清楚地了解到底发生了什么。它们将成为我们控制复杂性的最大希望之一。

Each topic area will explicitly introduce one or more sweeping simplifications. The reason is that they allow the designer to make compelling arguments for correctness, they make detail irrelevant, and they make clear to all participants exactly what is going on. They will turn out to be one of our best hopes for keeping control of complexity.

2.1.1. 记忆

2.1.1. Memory

内存，有时也称为存储，是用于记住数据值以供计算的系统组件。尽管内存技术范围很广，但正如图 2.1中的示例列表所示，所有内存设备都符合一个简单的抽象模型，该模型具有两个操作，即WRITE和READ：

Memory, sometimes called storage, is the system component that remembers data values for use in computation. Although memory technology is wide-ranging, as suggested by the list of examples in Figure 2.1, all memory devices fit a simple abstract model that has two operations, named WRITE and READ:

图 2.1一些可能熟悉的存储设备的示例。

Figure 2.1 Some examples of memory devices that may be familiar.

写入（名称，值）

WRITE (name, value)

值← READ (名称)

value ← READ (name)

WRITE操作在值中指定要记住的值，在名称中指定将来可以调用该值的名称。READ操作在名称中指定某个先前记住的值的名称，存储设备将返回该值。稍后调用指定相同名称的WRITE会更新与该名称关联的值。

The WRITE operation specifies in value a value to be remembered and in name a name by which one can recall that value in the future. The READ operation specifies in name the name of some previously remembered value, and the memory device returns that value. A later call to WRITE that specifies the same name updates the value associated with that name.

存储器可以是易失性的，也可以是非易失性的。易失性存储器的保存信息机制需要消耗能量；如果由于某种原因电源中断，存储器就会忘记其信息内容。当关闭非易失性存储器（有时称为“稳定存储器”）的电源时，存储器会保留其内容，当电源再次可用时，读取操作将返回与之前相同的值。通过将易失性存储器连接到电池或不间断电源，可以使存储器变得耐用，这意味着存储器被设计为至少在指定的一段时间内记住信息，这被称为耐用性。即使是非易失性存储器设备最终也会变质，这被称为衰减，因此它们通常也具有指定的耐用性，可能以年为单位。我们将在第 8 章 [在线] 和第 10 章 [在线] 中重新讨论耐用性，我们将在其中看到获得不同级别耐用性的方法。边栏 2.1将耐用性的含义与另外两个相关词进行了比较。

Memories can be either volatile or non-volatile. A volatile memory is one whose mechanism of retaining information consumes energy; if its power supply is interrupted for some reason, it forgets its information content. When one turns off the power to a non-volatile memory (sometimes called “stable storage”), it retains its content, and when power is again available, READ operations return the same values as before. By connecting a volatile memory to a battery or an uninterruptible power supply, it can be made durable, which means that it is designed to remember things for at least some specified period, known as its durability. Even non-volatile memory devices are subject to eventual deterioration, known as decay, so they usually also have a specified durability, perhaps measured in years. We will revisit durability in Chapters 8 [on-line] and 10 [on-line], where we will see methods of obtaining different levels of durability. Sidebar 2.1 compares the meaning of durability with two other, related words.

在物理层面，内存系统通常不会命名、读取或写入任意大小的值。相反，硬件层内存设备会读取和写入连续的位数组，这些数组通常长度固定，有各种术语称谓，如字节（通常为 8 位，但有时会遇到 6 位、7 位或 9 位字节的架构）、字（小整数个字节，通常为 2、4 或 8 个）、行（几个字）和块（通常是 2 的幂，可以以千为单位） 。无论数组大小如何，写入或读取的物理层内存的单位称为内存（或存储）单元。在大多数情况下，读取和写入调用中的名称参数实际上是单元的名称。更高层的内存系统也会读取和写入连续的位数组，但这些数组通常可以是任何方便的长度，并用记录、段或文件等术语来调用。

At the physical level, a memory system does not normally name, READ, or WRITE values of arbitrary size. Instead, hardware layer memory devices READ and WRITE contiguous arrays of bits, usually fixed in length, known by various terms such as bytes (usually 8 bits, but one sometimes encounters architectures with 6-, 7-, or 9-bit bytes), words (a small integer number of bytes, typically 2, 4, or 8), lines (several words), and blocks (a number of bytes, usually a power of 2, that can measure in the thousands). Whatever the size of the array, the unit of physical layer memory written or read is known as a memory (or storage) cell. In most cases, the name argument in the read and write calls is actually the name of a cell. Higher-layer memory systems also READ and WRITE contiguous arrays of bits, but these arrays usually can be of any convenient length, and are called by terms such as record, segment, or file.

2.1.2. 解释器

2.1.2. Interpreters

解释器是计算机系统的活跃元素；它们执行构成计算的操作。图 2.4列出了一些可能熟悉的解释器示例。与内存一样，解释器也有各种各样的物理表现形式。但是，它们也可以用一个简单的抽象来描述，仅由三个组件组成：

Interpreters are the active elements of a computer system; they perform the actions that constitute computations. Figure 2.4 lists some examples of interpreters that may be familiar. As with memory, interpreters also come in a wide range of physical manifestations. However, they too can be described with a simple abstraction, consisting of just three components:

图 2.4解释器的一些常见示例。磁盘控制器示例在2.3 节中进行了解释，而 Web 浏览器示例则是练习 4.5的主题。

Figure 2.4 Some common examples of interpreters. The disk controller example is explained in Section 2.3 and the Web browser examples are the subject of Exercise 4.5.

解释器的正常操作是按顺序执行某个程序，如图2.5的图表和伪代码所示。解释器使用环境引用找到当前环境，从该环境中检索指令引用中指示的程序指令。再次使用环境引用，解释器执行程序指令指示的操作。该操作通常涉及使用和更改环境中的数据，以及对指令引用进行适当更新。执行完指令后，解释器继续执行，将指令引用现在命名的指令作为下一条指令。某些事件（称为中断）可能会引起解释器的注意，导致它（而不是程序）提供下一条指令。原始程序不再控制解释器；相反，另一个程序（中断处理程序）接管并处理事件。解释器还可以将环境引用更改为适合中断处理程序的引用。

The normal operation of an interpreter is to proceed sequentially through some program, as suggested by the diagram and pseudocode of Figure 2.5. Using the environment reference to find the current environment, the interpreter retrieves from that environment the program instruction indicated in the instruction reference. Again using the environment reference, the interpreter performs the action directed by the program instruction. That action typically involves using and perhaps changing data in the environment, and also an appropriate update of the instruction reference. When it finishes performing the instruction, the interpreter moves on, taking as its next instruction the one now named by the instruction reference. Certain events, called interrupts, may catch the attention of the interpreter, causing it, rather than the program, to supply the next instruction. The original program no longer controls the interpreter; instead, a different program, the interrupt handler, takes control and handles the event. The interpreter may also change the environment reference to one that is appropriate for the interrupt handler.

图 2.5抽象解释器的结构和伪代码。实线箭头表示控制流，虚线箭头表示信息流。边栏 2.3描述了本书表达伪代码的惯例。

Figure 2.5 Structure of, and pseudocode for, an abstract interpreter. Solid arrows show control flow, and dashed arrows suggest information flow. Sidebar 2.3 describes this book’s conventions for expressing pseudocode.

许多系统都有多个解释器。多个解释器通常是异步的，这意味着它们在单独的、不协调的时钟上运行。因此，即使它们名义上相同并运行相同的程序，它们也可能以不同的速率进行。在设计协调多个解释器工作的算法时，通常假设它们的进度率之间没有固定的关系，因此无法预测相对时间，例如，它们发出的LOAD和STORE指令的相对时间。解释器异步的假设是内存读/写一致性和前后原子性可能成为具有挑战性的设计问题的原因之一。

Many systems have more than one interpreter. Multiple interpreters are usually asynchronous, which means that they run on separate, uncoordinated, clocks. As a result, they may progress at different rates, even if they are nominally identical and running the same program. In designing algorithms that coordinate the work of multiple interpreters, one usually assumes that there is no fixed relation among their progress rates and therefore that there is no way to predict the relative timing, for example, of the LOAD and STORE instructions that they issue. The assumption of interpreter asynchrony is one of the reasons memory read/write coherence and before-or-after atomicity can be challenging design problems.

2.1.3. 通讯链接

2.1.3. Communication Links

通信链路为信息在物理上分离的组件之间移动提供了一种方式。图 2.8列出了通信链路的一些示例，这些链路采用多种技术，但与内存和解释器一样，它们可以用简单的抽象来描述。通信链路抽象有两个操作：

A communication link provides a way for information to move between physically separated components. Communication links, of which a few examples are listed in Figure 2.8, come in a wide range of technologies, but, like memories and interpreters, they can be described with a simple abstraction. The communication link abstraction has two operations:

图 2.8一些通信链路的示例。

Figure 2.8 Some examples of communication links.

发送（链接名称，传出消息缓冲区）

SEND (link_name, outgoing_message_buffer)

接收（链接名称，传入消息缓冲区）

RECEIVE (link_name, incoming_message_buffer)

SEND操作指定一个位数组，称为消息，该数组将通过由link_name标识的通信链路（例如，线路）发送。参数outgoing_message_buffer标识要发送的消息，通常通过提供包含该消息的内存缓冲区的地址和大小来标识。RECEIVE操作接受传入消息，同样通常通过指定用于保存传入消息的内存缓冲区的地址和大小来接受。一旦系统的最低层收到消息，较高层可以通过调用较低层的RECEIVE接口来获取该消息，或者较低层可以“向上调用”较高层，在这种情况下，接口可能更好地描述为DELIVER（incoming_message）。

The SEND operation specifies an array of bits, called a message, to be sent over the communication link identified by link_name (for example, a wire). The argument outgoing_message_buffer identifies the message to be sent, usually by giving the address and size of a buffer in memory that contains the message. The RECEIVE operation accepts an incoming message, again usually by designating the address and size of a buffer in memory to hold the incoming message. Once the lowest layer of a system has received a message, higher layers may acquire the message by calling a RECEIVE interface of the lower layer, or the lower layer may “upcall” to the higher layer, in which case the interface might be better characterized as DELIVER (incoming_message).

名称以两种不同的方式将系统连接到通信链路。首先，SEND和RECEIVE的link_name参数标识连接到系统的可能多个可用通信链路之一。其次，一些通信链路实际上是多连接的链路网络，需要一些额外的方法来命名几个可能的接收者中的哪一个应该接收消息。预期接收者的名称通常是消息的组成部分之一。

Names connect systems to communication links in two different ways. First, the link_name arguments of SEND and RECEIVE identify one of possibly several available communication links attached to the system. Second, some communication links are actually multiply-attached networks of links, and some additional method is needed to name which of several possible recipients should receive the message. The name of the intended recipient is typically one of the components of the message.

乍一看，发送和接收消息似乎只是使用一系列READ和WRITE操作通过线路将一组位从一个内存复制到另一个内存的示例，因此不需要第三个抽象。然而，通信链路涉及的不仅仅是简单的复制——它们有很多复杂性，例如，各种各样的操作参数使得完成 SEND或RECEIVE操作的时间变得不可预测，恶劣的环境威胁着数据传输的完整性，异步操作导致无法提前知道消息的大小和传送时间，最重要的是，消息甚至可能没有被传送。由于这些复杂性，SEND和RECEIVE的语义通常与READ和WRITE相关的语义完全不同。调用SEND和RECEIVE的程序必须明确考虑这些不同的语义。另一方面，一些通信链路实现确实提供了一个层，它尽最大努力将SEND / RECEIVE接口隐藏在READ / WRITE接口后面。

At first glance, it might appear that sending and receiving a message is just an example of copying an array of bits from one memory to another memory over a wire using a sequence of READ and WRITE operations, so there is no need for a third abstraction. However, communication links involve more than simple copying—they have many complications, such as a wide range of operating parameters that makes the time to complete a SEND or RECEIVE operation unpredictable, a hostile environment that threatens integrity of the data transfer, asynchronous operation that leads to the arrival of messages whose size and time of delivery can not be known in advance, and most significant, the message may not even be delivered. Because of these complications, the semantics of SEND and RECEIVE are typically quite different from those associated with READ and WRITE. Programs that invoke SEND and RECEIVE must take these different semantics explicitly into account. On the other hand, some communication link implementations do provide a layer that does its best to hide a SEND/RECEIVE interface behind a READ/WRITE interface.

就像内存和解释器一样，设计人员分层组织和实现通信链路。我们不会在这里继续详细讨论通信链路，而是将其推迟到第 7.2 节 [在线]，该节描述了一个三层模型，该模型将通信链路组织成称为网络的系统。图 7.18 [在线] 说明了这个三层网络模型，它包括链路层、网络层和端到端层。

Just as with memory and interpreters, designers organize and implement communication links in layers. Rather than continuing a detailed discussion of communication links here, we defer that discussion to Section 7.2 [on-line], which describes a three-layer model that organizes communication links into systems called networks. Figure 7.18 [on-line] illustrates this three-layer network model, which comprises a link layer, a network layer, and an end-to-end layer.

2.2.1. 命名模型

2.2.1. The Naming Model

建立一个名称如何与特定对象关联的模型会很有帮助。系统设计人员创建一种命名方案，它由三个元素组成。第一个元素是名称空间，它由符号字母表和指定哪些名称可以接受的语法规则组成。第二个元素是名称映射算法，它将名称空间中的一些（不一定是全部）名称与值域中的一些（同样，不一定是全部）值相关联，这是命名方案的第三个也是最后一个元素。值可以是对象，也可以是来自原始名称空间或不同名称空间的另一个名称。名称到值的映射是绑定的一个示例，当存在这样的映射时，名称就被称作已绑定到值。图 2.10进行了说明。

It is helpful to have a model of how names are associated with specific objects. A system designer creates a naming scheme, which consists of three elements. The first element is a name space, which comprises an alphabet of symbols together with syntax rules that specify which names are acceptable. The second element is a name-mapping algorithm, which associates some (not necessarily all) names of the name space with some (again, not necessarily all) values in a universe of values, which is the third and final element of the naming scheme. A value may be an object, or it may be another name from either the original name space or from a different name space. A name-to-value mapping is an example of a binding, and when such a mapping exists, the name is said to be bound to the value. Figure 2.10 illustrates.

图 2.10命名方案操作的一般模型。名称映射算法接受一个名称和一个上下文，并从值域中返回一个元素。箭头表示，使用上下文“A”，算法将名称“N4”解析为值“13”。

Figure 2.10 General model of the operation of a naming scheme. The name-mapping algorithm takes in a name and a context, and it returns an element from the universe of values. The arrows indicate that, using context “A”, the algorithm resolves the name “N4” to the value “13”.

在大多数系统中，通常同​​时运行几种不同的命名方案。例如，系统可能使用一种命名方案来命名电子邮件邮箱名称，使用第二种命名方案来命名 Internet 主机，使用第三种命名方案来命名文件，使用第四种命名方案来命名虚拟内存地址。当程序解释器遇到名称时，它必须知道要调用哪种命名方案。名称的使用环境通常提供足够的信息来识别命名方案。例如，在应用程序中，该程序的作者知道该程序应该期望文件名仅由文件系统解释，而 Internet 主机名仅由某些网络服务解释。

In most systems, typically several distinct naming schemes are in operation simultaneously. For example, a system may be using one naming scheme for e-mail mailbox names, a second naming scheme for Internet hosts, a third for files, and a fourth for virtual memory addresses. When a program interpreter encounters a name, it must know which naming scheme to invoke. The environment surrounding use of the name usually provides enough information to identify the naming scheme. For example, in an application program, the author of that program knows that the program should expect file names to be interpreted only by the file system and Internet host names to be interpreted only by some network service.

遇到名称的解释器将运行相应命名方案的名称映射算法。名称映射算法会解析名称，这意味着它发现并返回关联值（因此，名称映射算法也称为解析器）。名称映射算法通常由一个附加参数控制，称为上下文。对于给定的命名方案，可能存在许多不同的上下文，当解析器使用不同的上下文时，名称空间的单个名称可能映射到不同的值。例如，在普通话语中，当某人提到“你”、“这里”或“爱丽丝”这些名字时，每个名字的含义取决于此人说出这些名字的上下文。另一方面，一些命名方案只有一个上下文。这样的命名方案提供所谓的通用名称空间，它们具有一个很好的特性，即无论谁使用名称，名称在该命名方案中始终具有相同的含义。例如，在美国，社会保障号码（用于识别政府养老金和税务账户）构成了一个通用名称空间。当存在多个上下文时，解释器可以告诉解析器应使用哪一个，或者解析器可以使用默认上下文。

The interpreter that encounters the name runs the name-mapping algorithm of the appropriate naming scheme. The name-mapping algorithm resolves the name, which means that it discovers and returns the associated value (for this reason, the name-mapping algorithm is also called a resolver). The name-mapping algorithm is usually controlled by an additional parameter, known as a context. For a given naming scheme, there can be many different contexts, and a single name of the name space may map to different values when the resolver uses different contexts. For example, in ordinary discourse when a person refers to the names “you”, “here”, or “Alice”, the meaning of each of those names depends on the context in which the person utters it. On the other hand, some naming schemes have only one context. Such naming schemes provide what are called universal name spaces, and they have the nice property that a name always has the same meaning within that naming scheme, no matter who uses it. For example, in the United States, social security numbers, which identify government pension and tax accounts, constitute a universal name space. When there is more than one context, the interpreter may tell the resolver which one it should use or the resolver may use a default context.

我们可以通过定义以下名称上的概念操作来总结命名模型：

We can summarize the naming model by defining the following conceptual operation on names:

值← RESOLVE (名称,上下文)

value ← RESOLVE (name, context)

当解释器在对象中遇到名称时，它首先会确定涉及的命名方案，从而确定应调用哪个版本的RESOLVE。然后，它会确定适当的上下文，在该上下文中解析名称，并在继续解释时用解析的值替换名称。变量context告诉RESOLVE要使用哪个上下文。该变量包含一个称为上下文引用的名称。

When an interpreter encounters a name in an object, it first figures out what naming scheme is involved and thus which version of RESOLVE it should invoke. It then identifies an appropriate context, resolves the name in that context, and replaces the name with the resolved value as it continues interpretation. The variable context tells RESOLVE which context to use. That variable contains a name known as a context reference.

在处理器中，寄存器编号就是名称。在简单的处理器中，寄存器名称集以及这些名称绑定到的寄存器都是在设计时固定的。在大多数使用名称的其他系统中（包括某些高性能处理器的寄存器命名方案），可以创建新的绑定并删除旧的绑定，枚举名称空间以获取现有绑定的列表，并比较两个名称。为此，我们定义了另外四个概念操作：

In a processor, register numbers are names. In a simple processor, the set of register names, and the registers those names are bound to, are both fixed at design time. In most other systems that use names (including the register naming scheme of some high-performance processors), it is possible to create new bindings and delete old ones, enumerate the name space to obtain a list of existing bindings, and compare two names. For these purposes we define four more conceptual operations:

状态← BIND（名称，值，上下文）

status ← BIND (name, value, context)

状态← UNBIND（名称，上下文）

status ← UNBIND (name, context)

列表← ENUMERATE（上下文）

list ← ENUMERATE (context)

结果←比较（名称1，名称2）

result ← COMPARE (name1, name2)

第一个操作通过添加新绑定来更改上下文；状态结果报告更改是否成功（如果提议的名称违反了名称空间的语法规则，更改可能会失败）。成功调用BIND后，RESOLVE将返回name的新值。^*第二个操作UNBIND从上下文中删除现有绑定，状态再次报告成功或失败（可能是因为没有这样的现有绑定）。成功调用UNBIND后，RESOLVE将不再返回name的该值。BIND和UNBIND操作允许使用名称在对象之间建立连接并在以后更改这些连接。对象的设计者可以使用名称来引用组件对象，通过调用 BIND 在当时或以后选择该名称绑定到的对象，并通过调用UNBIND消除不再合适的绑定，所有这些都无需修改使用该名称的对象。这种延迟和更改绑定的能力是几乎所有系统设计中使用的强大工具。一些命名实现提供了ENUMERATE操作，该操作返回context中可以解析的所有名称的列表。ENUMERATE的一些实现还可以返回context中当前绑定的所有值的列表。最后，COMPARE操作报告（TRUE或FALSE ） name1是否与name2相同。“相同”的含义是一个有趣的问题，将在2.2.5 节中讨论，它可能需要提供额外的上下文参数。

The first operation changes context by adding a new binding; the status result reports whether or not the change succeeded (it might fail if the proposed name violates the syntax rules of the name space). After a successful call to BIND, RESOLVE will return the new value for name.^* The second operation, UNBIND, removes an existing binding from context, with status again reporting success or failure (perhaps because there was no such existing binding). After a successful call to UNBIND, RESOLVE will no longer return that value for name. The BIND and UNBIND operations allow the use of names to make connections between objects and change those connections later. A designer of an object can, by using a name to refer to a component object, choose the object to which that name is bound either then or at a later time by invoking BIND, and eliminate a binding that is no longer appropriate by invoking UNBIND, all without modifying the object that uses the name. This ability to delay and change bindings is a powerful tool used in the design of nearly all systems. Some naming implementations provide an ENUMERATE operation, which returns a list of all the names that can be resolved in context. Some implementations of ENUMERATE can also return a list of all values currently bound in context. Finally, the COMPARE operation reports (TRUE or FALSE) whether or not name1 is the same as name2. The meaning of “same” is an interesting question addressed in Section 2.2.5, and it may require supplying additional context arguments.

不同的命名方案对名称到值映射的唯一性有不同的规则。有些命名方案有这样的规则：在给定上下文中，名称必须映射到一个值，并且值必须只有一个名称；而在其他命名方案中，即使在同一个上下文中，一个名称也可以映射到多个值，或者一个值可以有多个名称。另一种唯一性规则是唯一标识符名称空间的规则，它提供了一组名称，这些名称在名称空间的生命周期内永远不会被重复使用，并且一旦绑定，将始终绑定到相同的值。这样的名称被称为具有稳定绑定。如果唯一标识符名称空间还具有一个值只能有一个名称的规则，则唯一名称对于长期跟踪对象、比较引用以查看它们是否指向同一个对象以及在为了提高性能或可靠性而复制对象的系统中协调多个副本非常有用。例如，大多数计费系统的客户帐号构成了一个唯一标识符名称空间。只要账户存在，帐号就始终指向同一个客户账户，无论客户的地址、电话号码甚至个人姓名如何变化。如果删除了客户的账户，该客户的帐号不会在某一天被重新用于其他客户的账户。账户内的命名字段（例如应付余额）可能会不时发生变化，但客户帐号与账户本身之间的绑定是稳定的。

Different naming schemes have different rules about the uniqueness of name-to-value mappings. Some naming schemes have a rule that a name must map to exactly one value in a given context and a value must have only one name, while in other naming schemes one name may map to several values, or one value may have several names, even in the same context. Another kind of uniqueness rule is that of a unique identifier name space, which provides a set of names that will never be reused for the lifetime of the name space and, once bound, will always remain bound to the same value. Such a name is said to have a stable binding. If a unique identifier name space also has the rule that a value can have only one name, the unique names become useful for keeping track of objects over a long period of time, for comparing references to see if they are to the same object, and for coordination of multiple copies in systems where objects are replicated for performance or reliability. For example, the customer account number of most billing systems constitutes a unique identifier name space. The account number will always refer to the same customer’s account as long as that account exists, despite changes in the customer’s address, telephone number, or even personal name. If a customer’s account is deleted, that customer’s account number will not someday be reused for a different customer’s account. Named fields within the account, such as the balance due, may change from time to time, but the binding between the customer account number and the account itself is stable.

名称映射算法加上单个上下文不一定将名称空间的所有名称映射到值。因此，执行RESOLVE的一个可能结果可能是未找到结果，RESOLVE可能会将其作为保留值或异常传达给调用者。另一方面，如果命名方案允许一个名称映射到多个值，则可能的结果可能是值的列表。在这种情况下，UNBIND操作可能需要一个附加参数来指定要解除绑定的值。最后，一些命名方案提供反向查找，这意味着调用者可以将值作为参数提供给名称映射算法，并找出与该值绑定的名称。

The name-mapping algorithm plus a single context do not necessarily map all names of the name space to values. Thus, a possible outcome of performing RESOLVE can be a not-found result, which RESOLVE may communicate to the caller either as a reserved value or as an exception. On the other hand, if the naming scheme allows one name to map to several values, a possible outcome can be a list of values. In that case, the UNBIND operation may require an additional argument that specifies which value to unbind. Finally, some naming schemes provide reverse lookup, which means that a caller can supply a value as an argument to the name-mapping algorithm, and find out what name or names are bound to that value.

图 2.10说明了命名模型，显示了名称空间、相应的值域、名称映射算法以及控制名称映射算法的上下文。

Figure 2.10 illustrates the naming model, showing a name space, the corresponding universe of values, a name-mapping algorithm, and a context that controls the name-mapping algorithm.

在实践中，人们会遇到三种常用的名称映射算法：

In practice, one encounters three frequently used name-mapping algorithms:

上下文的最常见实现是{名称,值}对的表。当上下文的实现是表时，名称映射算法只是在该表中查找名称。表本身可能很复杂，涉及哈希或 B 树，但基本思想仍然相同。将新名称绑定到值包括将{名称,值}对添加到表中。图 2.11说明了命名模型的这种常见实现。每个上下文都有一个这样的表，不同的上下文可能包含相同名称的不同绑定。

The most common implementation of a context is a table of {name, value} pairs. When the implementation of a context is a table, the name-mapping algorithm is just a lookup of the name in that table. The table itself may be complex, involving hashing or B-trees, but the basic idea is still the same. Binding a new name to a value consists of adding that {name, value} pair to the table. Figure 2.11 illustrates this common implementation of the naming model. There is one such table for each context, and different contexts may contain different bindings for the same name.

图 2.11使用表查找作为名称映射算法的系统。与图 2.10的示例一样，该系统也将名称“N4”解析为值“13”。

Figure 2.11 A system that uses table lookup as the name-mapping algorithm. As in the example of Figure 2.10, this system also resolves the name “N4” to the value “13”.

现实世界中通用命名模型和表查找实现的例子比比皆是：

Real-world examples of both the general naming model and the table-lookup implementation abound:

这些例子也强调了“命名”和绑定之间的区别。有些（但不是全部）上下文会“命名”事物，即它们将名称映射到通常认为具有该名称的对象。因此，电话簿不会“命名”人或电话线路。在其他地方，有些上下文会将名称绑定到人，将电话号码绑定到特定的物理电话。电话簿将人的名字与电话名称绑定在一起。

These examples also highlight a distinction between “naming” and binding. Some, but not all, contexts “name” things, in the sense that they map a name to an object that is commonly thought of as having that name. Thus, the telephone directory does not “name” either people or telephone lines. Somewhere else there are contexts that bind names to people and that bind telephone numbers to particular physical phones. The telephone directory binds the names of people to the names of telephones.

对于每个示例，上下文引用必须标识名称映射算法应在其中解析名称的上下文。接下来，我们探索上下文引用来自何处。

For each of these examples a context reference must identify the context in which the name-mapping algorithm should resolve the name. Next, we explore where context references come from.

2.2.2. 默认和显式上下文引用

2.2.2. Default and Explicit Context References

当程序解释器遇到对象中的名称时，必须有人提供上下文引用，以便名称映射算法知道应使用哪个上下文来解析名称。命名中许多看似令人费解的问题都可以简单地诊断出来：名称映射算法出于某种原因使用了错误的上下文引用。

When a program interpreter encounters a name in an object, someone must supply a context reference so that the name-mapping algorithm can know which context it should use to resolve the name. Many apparently puzzling problems in naming can be simply diagnosed: the name-mapping algorithm, for whatever reason, used the wrong context reference.

有两种方法可以提出一个上下文来解析对象中找到的名称：默认和显式。默认上下文引用是解析器提供的引用，而显式上下文引用是与使用名称的对象一起打包的引用。有时命名方案允许使用显式和默认方法：如果对象或名称提供了显式上下文引用，则它使用显式上下文引用；如果没有，则使用默认上下文。图 2.12概述了接下来两段中描述的上下文引用的分类。

There are two ways to come up with a context with which to resolve the names found in an object: default and explicit. A default context reference is one that the resolver supplies, whereas an explicit context reference is one that comes packaged with the name-using object. Sometimes a naming scheme allows for use of both explicit and default methods: it uses an explicit context reference if the object or name provides one; if not, it uses a default context. Figure 2.12 outlines the taxonomy of context references described in the next two paragraphs.

图 2.12上下文引用的分类。

Figure 2.12 Taxonomy of context references.

默认上下文引用可以是解析器在设计时内置的一个常量。由于一个常量只允许一个上下文，因此生成的命名空间是通用的。或者，默认上下文引用可以是解析器从其当前执行环境中获取的一个变量。该变量可以由某些上下文分配规则设置。例如，在大多数多用户系统中，每个用户的执行环境都包含一个称为工作目录的状态变量。工作目录充当解析文件名的默认上下文。类似地，系统可以为用户的每个不同活动分配一个默认上下文，甚至可以为系统的每个主要子系统分配默认上下文（如第 3 章（图 3.2和3.3 ）中所示） 。

A default context reference can be a constant that is built in to the resolver as part of its design. Since a constant allows for just one context, the resulting name space is universal. Alternatively, a default context reference can be a variable that the resolver obtains from its current execution environment. That variable may be set by some context assignment rule. For example, in most multiple-user systems, each user’s execution environment contains a state variable called the working directory. The working directory acts as the default context for resolving file names. Similarly, the system may assign a default context for each distinct activity of a user or even, as will be seen in Chapter 3 (Figures 3.2 and 3.3), for each major subsystem of a system.

相比之下，显式上下文引用通常有两种形式：用于对象使用的所有名称的单上下文引用，或与对象中每个名称相关联的不同上下文引用。第二种形式，其中每个名称都与其自己的上下文引用一起打包，称为限定名称。

In contrast, an explicit context reference commonly comes in one of two forms: a single-context reference intended to be used for all the names that an object uses, or a distinct context reference associated with each name in the object. The second form, in which each name is packaged with its own context reference, is known as a qualified name.

上下文引用本身就是一个名称（它命名上下文），这导致一些作者将其描述为基本名称。因此，名称解析器必须先解析上下文引用所表示的名称，然后才能继续进行原始名称解析。此递归可以重复多次，但它必须在某处终止，即调用具有单个内置上下文的名称解析器。此内置上下文包含允许解开递归的绑定。

A context reference is itself a name (it names the context), which leads some writers to describe it as a base name. The name resolver must thus resolve the name represented by the context reference before it can proceed with the original name resolution. This recursion may be repeated several times, but it must terminate somewhere, with the invocation of a name resolver that has a single built-in context. This built-in context contains the bindings that permit the recursion to be unraveled.

这个描述相当抽象。为了使其具体化，让我们重新回顾之前现实世界中的名称示例，在每种情况下寻找解析器使用的上下文引用：

That description is quite abstract. To make it concrete, let’s revisit the previous real-world examples of names, in each case looking for the context reference the resolver uses:

上下文引用可以是动态的，这意味着它会随时间而变化。例如，当用户单击标有“帮助”的菜单按钮时。尽管按钮可能始终出现在屏幕上的同一位置，但解析名称“帮助”的上下文（以及响应中显示的特定帮助屏幕）可能取决于用户单击按钮时正在运行的应用程序，甚至该程序的哪个部分。

A context reference can be dynamic, meaning that it changes from time to time. An example is when the user clicks on a menu button labeled “Help”. Although the button may always appear in the same place on the screen, the context in which the name “Help” is resolved (and thus the particular help screen that appears in response) is likely to depend on which application program, or even which part of that program, is running at the instant that the user clicks on the button.

一个常见问题是使用名称的对象没有提供显式上下文，而名称解析器选择了错误的默认上下文。例如，文件系统通常根据当前工作目录解析文件名，即使此工作目录可能与进行引用的程序或数据对象的身份无关。与编程系统的名称解析环境相比，大多数文件系统提供的名称解析机制相当原始。

A common problem is that the object that uses a name does not provide an explicit context, and the name resolver chooses the wrong default context. For example, a file system typically resolves a file name relative to a current working directory, even though this working directory may be unrelated to the identity of the program or data object making the reference. Compared with the name resolution environment of a programming system, most file systems provide a rather primitive name resolution mechanism.

电子邮件系统提供了一个确保名称在预期上下文中得到解释的问题示例。考虑图 2.13中的电子邮件消息，该消息源自 Pedantic 大学。在此消息中，Alice、Bob和Dawn是来自 Pedantic 大学电子邮箱本地名称空间的名称，而Charles@cse.Scholarly.edu是学术研究所名为cse.Scholarly.edu的邮件服务管理的电子邮箱的限定名称。名称Charles是该邮件服务中的一个特定邮箱的名称，@ 符号通常用于将邮箱名称与邮件服务名称分开。

An electronic mail system provides an example of the problem of making sure that names are interpreted in the intended context. Consider the e-mail message of Figure 2.13, which originated at Pedantic University. In this message, Alice, Bob, and Dawn are names from the local name space of e-mailboxes at Pedantic University, and Charles@cse.Scholarly.edu is a qualified name of an e-mailbox managed by a mail service named cse.Scholarly.edu at the Institute of Scholarly Studies. The name Charles is of a particular mailbox at that mail service, and the @-sign is conventionally used to separate the name of the mailbox from the name of the mail service.

图 2.13使用默认上下文的电子邮件。

Figure 2.13 An e-mail message that uses default contexts.

目前，如果用户Charles尝试回复此消息的发件人，则响应将发送给Bob。由于遇到回复消息的第一个名称解析器可能位于名为cse.Scholarly.edu的系统内部，因此该解析器通常会使用本地邮件服务的名称作为默认上下文引用。也就是说，它会尝试将消息发送到Bob@cse.Scholarly.edu。这不是发送原始消息的用户的邮箱地址。更糟糕的是，它可能是其他人的邮箱地址。

As it stands, if user Charles tries to reply to the sender of this message, the response will be addressed to Bob. Since the first name resolver to encounter the reply message is probably inside the system named cse.Scholarly.edu, that resolver would in the normal course of events use as a default context reference the name of the local mail service. That is, it would try to send the message to Bob@cse.Scholarly.edu. That isn’t the mailbox address of the user who sent the original message. Worse, it might be someone else’s mailbox address.

在构造电子邮件消息时，Alice 希望在自己的上下文中解析诸如Bob之类的本地名称。大多数邮件发送系统都知道本地名称对本地上下文之外的任何人都没有用处，因此邮件系统通常会修改地址字段中发现的非限定名称，方法是自动将其重写为限定名称，从而为名称Bob和Alice添加显式上下文引用，如图2.14所示。

When constructing the e-mail message, Alice intended local names such as Bob to be resolved in her own context. Most mail sending systems know that a local name is not useful to anyone outside the local context, so it is conventional for the mail system to tinker with unqualified names found in the address fields by automatically rewriting them as qualified names, thus adding an explicit context reference to the names Bob and Alice, as shown in Figure 2.14.

图 2.14图 2.13中的电子邮件消息，在邮件系统扩展标题中的每个不合格地址以包含明确的上下文引用之后。

Figure 2.14 The e-mail message of Figure 2.13 after the mail system expands every unqualified address in the headers to include an explicit context reference.

不幸的是，邮件系统只能对标题执行此地址重写，因为这是邮件格式中它完全理解的唯一部分。如果电子邮件地址嵌入在邮件文本中（如示例中的邮箱名称Dawn），邮件系统就无法将其与其他文本区分开来。如果邮件收件人希望使用邮件文本中找到的电子邮件地址，则该收件人必须弄清楚需要什么上下文参考。有时很容易弄清楚该怎么做，但如果邮件已被转发几次，或者收件人没有意识到问题，则可能会出错。

Unfortunately, the mail system can perform this address rewriting only for the headers because that is the only part of the message format it fully understands. If an e-mail address is embedded in the text of the message (as in the example, the mailbox name Dawn), the mail system has no way to distinguish it from the other text. If the recipient of the message wishes to make use of an e-mail address found in the text of the message, that recipient is going to have to figure out what context reference is needed. Sometimes it is easy to figure out what to do, but if a message has been forwarded a few times, or the recipient is unaware of the problem, a mistake is likely.

部分解决方案可以是使用额外的标题为电子邮件消息添加显式上下文引用，如图2.15所示。通过此附加内容，此消息的收件人可以选择标题中的Alice或文本中的Dawn ，并要求邮件系统发送回复。邮件系统可以通过检查Context:标题来确定如何解析与此消息相关的任何不合格电子邮件地址，无论是在原始标题中找到还是从消息文本中提取。此方案非常临时；如果用户Bob将图 2.15中的消息连同附加注释一起转发给另一个命名上下文中的某人，则附加注释中的任何不合格地址都需要不同的显式上下文引用。虽然作者所知的任何电子邮件系统都没有实际使用此方案，但它已在其他命名系统中使用。一个例子是 HTML 的基本元素，万维网的显示语言，在第3.2.2 节中简要介绍。

A partial solution could be to tag the e-mail message with an explicit context reference, using an extra header, as in Figure 2.15. With this addition, a recipient of this message could select either Alice in the header or Dawn in the text and ask the mail system to send a reply. The mail system could, by examining the Context: header, determine how to resolve any unqualified e-mail address associated with this message, whether found in the original headers or extracted from the text of the message. This scheme is quite ad hoc; if user Bob forwards the message of Figure 2.15 with an added note to someone in yet another naming context, any unqualified addresses in the added note would need a different explicit context reference. Although this scheme is not actually used in any e-mail system that the authors are aware of, it has been used in other naming systems. An example is the base element of HTML, the display language of the World Wide Web, described briefly in Section 3.2.2.

图 2.15一封电子邮件，其中提供了明确的上下文引用作为其标题之一。

Figure 2.15 An e-mail message that provides an explicit context reference as one of its headers.

一个密切相关的问题是，不同的上下文可能为同一对象绑定不同的名称。例如，要拨打某个电话，同一组织中的一个人可能拨打 2-7104，城市另一端的第二个人拨打 312-7104，稍远的第三个人拨打 (517) 312-7104，而另一个国家的人可能必须拨打 001 (517) 312-7104。当同一对象在不同上下文中具有不同的名称时，将名称从一个用户传递给另一个用户会很尴尬，因为与电子邮件消息示例一样，必须有人翻译该名称，然后其他用户才能使用它。与电子邮件地址一样，如果有人递给你一张写有电话号码 312-7104 的纸片，那么简单地拨打该号码可能会或可能不会拨打目标电话。即使几个名称是相关的，也可能需要付出一些努力才能弄清楚到底需要进行什么翻译。

A closely related problem is that different contexts may bind different names for the same object. For example, to call a certain telephone, it may be that a person in the same organization dials 2-7104, a second person across the city dials 312-7104, a third who is a little farther away dials (517) 312-7104, and a person in another country may have to dial 001 (517) 312-7104. When the same object has different names in different contexts, passing a name from one user to another is awkward because, as with the e-mail message example, someone must translate the name before the other user can use it. As with the e-mail address, if someone hands you a scrap of paper on which is written the telephone number 312-7104, simply dialing that number may or may not ring the intended telephone. Even though the several names are related, some effort may be required to figure out just what translation is required.

2.2.3. 路径名、命名网络和递归名称解析

2.2.3. Path Names, Naming Networks, and Recursive Name Resolution

第 64 页列出的三种常见名称映射算法中的第二种是递归名称解析。路径名可以被认为是明确包含对其应解析的上下文的引用的名称。在某些命名方案中，路径名以上下文引用在前的方式书写，在其他命名方案中，以上下文引用在后的方式书写。以下是一些路径名示例：

The second of the three common name-mapping algorithms listed on page 64 is recursive name resolution. A path name can be thought of as a name that explicitly includes a reference to the context in which it should be resolved. In some naming schemes, path names are written with the context reference first, in others with the context reference last. Some examples of path names are:

ginger.pedantic.edu。

ginger.pedantic.edu.

/usr/bin/emacs

/usr/bin/emacs

Macintosh HD:项目:CSE 496:问题集 1

Macintosh HD:projects:CSE 496:problem set 1

第 2 章第 2 节第 3 部分第一段

Chapter 2, section 2, part 3, first paragraph

第2章第2节第3部分第1款

Paragraph 1 of part 3 of section 2 of chapter 2

正如这些示例所示，路径名涉及多个组件和一些允许名称解析器解析组件的语法。最后两个示例说明，不同的命名方案将组件名称置于相反的顺序，而其他示例也确实展示了这两种顺序。名称的用户和名称解析器必须知道组件的顺序，但无论哪种方式，路径名的解释最容易通过借用数字表示中的术语来递归解释：路径名中除最不重要的组件之外的所有组件都是显式上下文引用，用于标识用于解析该最不重要的组件的上下文。在上述示例中，最不重要的组件及其显式上下文引用分别是

As these examples suggest, a path name involves multiple components and some syntax that permits a name resolver to parse the components. The last two examples illustrate that different naming schemes place the component names in opposite orders, and indeed the other examples also demonstrate both orders. The order of the components must be known to the user of the name and to the name resolver, but either way interpretation of the path name is most easily explained recursively by borrowing terminology from the representation of numbers: all but the least significant component of a path name is an explicit context reference that identifies the context to be used to resolve that least significant component. In the above examples, the least significant components and their explicit context references are, respectively,

最低有效成分显式上下文引用

Least significant component Explicit context reference

ginger pedantic.edu。

ginger pedantic.edu.

emacs /usr/bin

emacs /usr/bin

问题集 1 Macintosh hd:projects:CSE 491

problem set 1 Macintosh hd:projects:CSE 491

第一段 第 2 章第 2 节第 3 部分

first paragraph Chapter 2, section 2, part 3

第2章第2节第3部分第1款

Paragraph 1 part 3 of section 2 of chapter 2

此描述的递归方面是显式上下文引用本身就是必须解析的路径名。因此，我们根据需要重复分析多次，直到路径名中原本最重要的部分也成为最不重要的部分，此时解析器可以使用某个上下文进行普通的表查找。在选择此上下文时，先前关于默认和显式上下文引用的讨论再次适用。在典型设计中，解析器使用两个默认上下文引用之一：

The recursive aspect of this description is that the explicit context reference is itself a path name that must be resolved. So we repeat the analysis as many times as needed until what was originally the most significant component of the path name is also the least significant component, at which point the resolver can do an ordinary table lookup using some context. In the choice of this context, the previous discussion of default and explicit context references again applies. In a typical design, the resolver uses one of two default context references:

如果准备使用单个名称解析器来解析相对路径名和绝对路径名，则某些方案（例如，语法标志）（例如，/usr/bin/emacs中的初始“ / ”和ginger.pedantic.edu.中的终端“ . ” ）可能会将两者区分开来，或者名称解析器可能会按某种顺序尝试两种方式，并使用似乎有效的第一种。按顺序尝试两种方案是多名称查找的一种简单形式，我们将在下一小节中详细介绍。

If a single name resolver is prepared to resolve both relative and absolute path names, some scheme such as a syntactic flag (e.g., the initial “/” in /usr/bin/emacs and the terminal “.” in ginger.pedantic.edu.) may distinguish one from the other, or perhaps the name resolver will try both ways in some order, using the first one that seems to work. Trying two schemes in order is a simple form of multiple name lookup, about which we will have more to say in the next subsection.

路径名也可以被认为是组织在所谓命名网络中的标识对象。在命名网络中，上下文被视为对象，任何上下文都可能包含任何其他对象（包括另一个上下文）的名称到对象绑定。名称解析器以某种方式选择一个上下文作为根（可能通过将该上下文的低级名称连接到解析器），然后通过跟踪从所选根到路径名中第一个命名上下文的路径来解析所有绝对路径名，然后再跟踪下一个上下文，继续下去，直到到达由原始路径名命名的对象。它类似地解析相对路径名，从其环境中的变量中找到的默认上下文开始。该变量包含默认上下文的绝对路径名。由于从一个地方到另一个地方可以有多条路径，因此同一对象或上下文可以有许多不同的路径名。同一对象的多个名称称为同义词或别名。 （本文避免使用“别名”一词，因为不同的系统使用该词的方式截然不同。）另一方面，由于根提供了一个通用名称空间，因此每个使用相同绝对路径名的对象都引用相同的导出对象。

Path names can also be thought of as identifying objects that are organized in what is called a naming network. In a naming network, contexts are treated as objects, and any context may contain a name-to-object binding for any other object, including another context. The name resolver somehow chooses one context to use as the root (perhaps by having a lower-level name for that context wired into the resolver), and it then resolves all absolute path names by tracing a path from the chosen root to the first named context in the path name, then the next, continuing until it reaches the object that was named by the original path name. It similarly resolves relative path names starting with a default context found in a variable in its environment. That variable contains the absolute path name of the default context. Since there can be many paths from one place to another, there can be many different path names for the same object or context. Multiple names for the same object are known as synonyms or aliases. (This text avoids the word “alias” because different systems use it in quite different ways.) On the other hand, since the root provides a universal name space, every object that uses the same absolute path name is referring to the same exporting object.

共享命名网络的名称可能会带来问题，因为每个用户可能表达相对于不同起点的路径名。因此，在将路径名从一个用户传递到另一个用户时，如何转换路径名可能并不明显。解决此问题的一个标准方法是要求用户仅共享绝对路径名，所有路径名均以根开头。

Sharing names of a naming network can be a problem because each user may express path names relative to a different starting point. As a result, it may not be obvious how to translate a path name when passing it from one user to another. One standard solution to this problem is to require that users share only absolute path names, all of which begin with the root.

计算机操作系统的文件系统通常组织为命名网络，其中目录充当上下文。在文件系统中，经常会遇到由实现驱动的对命名网络形状的限制，例如，要求上下文按命名层次结构组织，其中根充当树的底部。真正的命名层次结构非常严格，在实践中很少见到；实际系统即使表面上是层次化的，通常也会提供某种添加跨层次结构链接的方法。最简单的链接就是同义词：一个对象可能绑定在多个上下文中。某些系统允许一种更复杂的链接，称为间接名称。间接名称是上下文绑定到同一名称空间中的另一个名称而不是对象的名称。由于许多设计人员已经独立意识到间接名称很有用，因此它们有许多不同的标签，包括符号链接、软链接、别名和快捷方式。2.5 节中描述的UNIX文件系统包括命名层次结构、链接和称为软链接的间接名称。

The file system of a computer operating system is usually organized as a naming network, with directories acting as contexts. It is common in file systems to encounter implementation-driven restrictions on the shape of the naming network, for example, requiring that the contexts be organized in a naming hierarchy with the root acting as the base of the tree. A true naming hierarchy is so constraining that it is rarely found in practice; real systems, even if superficially hierarchical, usually provide some way of adding cross-hierarchy links. The simplest kind of link is just a synonym: a single object may be bound in more than one context. Some systems allow a more sophisticated kind of link, known as an indirect name. An indirect name is one that a context binds to another name in the same name space rather than to an object. Because many designers have independently realized that indirect names are useful, they have come to be called by many different labels, including symbolic link, soft link, alias, and shortcut. The UNIX file system described in Section 2.5 includes a naming hierarchy, links, and indirect names called soft links.

路径名具有内部结构，因此支持路径名的命名方案通常具有关于允许的路径名的构造的规则。路径名可能有最大长度，并且某些符号可能被限制仅用作结构分隔符。

A path name has internal structure, so a naming scheme that supports path names usually has rules regarding construction of allowable path names. Path names may have a maximum length, and certain symbols may be restricted for use only as structural separators.

2.2.4. 多重查找：通过分层上下文进行搜索

2.2.4. Multiple Lookup: Searching through Layered Contexts

回到默认上下文的主题（图 2.12的分类法中），上下文分配规则是一种钝化工具。例如，包含库程序的目录可能需要在不同用户之间共享；没有一条分配规则可以满足需要。这种不灵活性导致了第三种更复杂的名称解析方案，即多重查找。^*多重查找的思想是放弃单一默认上下文的概念，而是通过系统地尝试几个不同的上下文来解析名称。由于名称可能绑定在多个上下文中，因此多重查找可以产生多个解析，因此需要某种方案来决定使用哪种解析。

Returning to the topic of default contexts (in the taxonomy of Figure 2.12), context assignment rules are a blunt tool. For example, a directory containing library programs may need to be shared among different users; no single assignment rule can suffice. This inflexibility leads to the third, more elaborate name resolution scheme, multiple lookup.^* The idea of multiple lookup is to abandon the notion of a single, default context and instead resolve the name by systematically trying several different contexts. Since a name may be bound in more than one context, multiple lookup can produce multiple resolutions, so some scheme is needed to decide which resolution to use.

一种常见的此类方案称为搜索路径，它只不过是按顺序尝试的特定上下文列表。名称解析器尝试使用列表中的第一个上下文来解析名称。如果未找到结果，它会尝试下一个上下文，依此类推。如果名称绑定在列出的多个上下文中，则列表中最早的上下文获胜，解析器返回与该绑定关联的值。

A common such scheme is called the search path, which is nothing more than a specific list of contexts to be tried, in order. The name resolver tries to resolve the name using the first context in the list. If it gets a not-found result, it tries the next context, and so on. If the name is bound in more than one of the listed contexts, the one earliest in the list wins and the resolver returns the value associated with that binding.

搜索路径通常用于具有库的编程系统中。例如，假设计算平方根数学函数的库过程导出一个名为SQRT的过程接口。编译此函数后，编写者将二进制程序的副本放在数学库中。平方根函数的潜在用户会写下语句

A search path is often used in programming systems that have libraries. Suppose, for example, a library procedure that calculates the square root math function exports a procedure interface named SQRT. After compiling this function, the writer places a copy of the binary program in a math library. A prospective user of the square root function writes the statement

x ← SQRT ( y )

x ← SQRT(y)

在程序中，编译器生成使用名为SQRT的过程的代码。下一步是编译器（或在某些系统中为稍后的加载器）在它知道的各种公共和私有库中进行一系列查找。每个库都是一个上下文，搜索路径是库上下文的列表。多重查找的每一步都涉及调用更简单的单上下文名称解析器。其中一些尝试的解析可能会返回未找到的结果。第一次找到名为SQRT的程序的解析尝试将返回该程序作为查找的结果。

in a program, and the compiler generates code that uses the procedure named SQRT. The next step is that the compiler (or in some systems a later loader) undertakes a series of lookups in various public and private libraries that it knows about. Each library is a context, and the search path is a list of the library contexts. Each step of the multiple lookup involves an invocation of a simpler, single-context name resolver. Some of these attempted resolutions will probably return a not-found result. The first resolution attempt that finds a program named SQRT will return that program as the result of the lookup.

搜索路径通常以每个用户列表的形式实现，用户可以设置其中的部分或全部元素。通过将包含个人提供的程序的库放在搜索路径的早期，单个用户可以有效地将一个库程序替换为另一个同名的库程序，从而提供依赖于用户的绑定。此按名称替换功能很有用，但也可能很危险，因为用户可能会无意中选择某个程序的名称，而该程序也由某个完全不相关的库程序导出。当其他应用程序尝试调用该不相关的程序时，随后的多次查找可能会找到错误的程序。随着搜索路径中的库和名称数量的增加，两个库意外包含两个恰好导出相同名称的不相关程序的可能性也会增加。

A search path is usually implemented as a per-user list, some or all of whose elements the user can set. By placing a library that contains personally supplied programs early in the search path, an individual user can effectively replace a library program with another that has the same name, thereby providing a user-dependent binding. This replace-by-name feature can be useful, but it can also be hazardous because one may unintentionally choose a name for a program that is also exported by some completely unrelated library program. When some other application tries to call that unrelated program, the ensuing multiple lookup may find the wrong one. As the number of libraries and names in the search path increases, the chance increases that two libraries will accidentally contain two unrelated programs that happen to export the same name.

尽管存在危险，搜索路径仍是一种广泛使用的机制。除了加载器使用搜索路径来定位库过程之外，用户界面也使用搜索路径来定位用户输入名称的命令，编译器使用搜索路径来定位界面，文档系统使用搜索路径来查找引用的文档，文字处理系统使用搜索路径来定位要包含在当前文档中的文本片段。

Despite the hazards, search paths are a widely used mechanism. In addition to loaders using search paths to locate library procedures, user interfaces use search paths to locate commands whose names the user typed, compilers use search paths to locate interfaces, documentation systems use search paths to find cited documents, and word processing systems use search paths to locate text fragments to be included in the current document.

一些命名方案使用更受限制的多重查找方法。例如，命名方案可能要求将上下文排列在嵌套层中，而不是允许任意上下文列表。每当解析返回某个层中未找到时，解析器就会在封闭层中重试。分层上下文曾经在编程语言中很流行，程序在其中定义和调用子程序，因为允许子程序通过名称访问定义或调用程序的变量可能很方便（甚至不守规矩，这就是它不再那么流行的原因）。再举一个例子，用于对 Internet 网络连接点进行编号的方案具有外部公共层和内部私有层。某些 Internet 地址范围（例如，所有第一个字节为 10 的地址）保留用于私有网络；这些地址范围构成内部私有层。这些网络地址可以绑定到不同私有上下文中的不同网络连接点，而不会发生冲突。超出为私有上下文保留的范围的 Internet 地址不应绑定在任何私有上下文中；这些问题都是在公共背景下得到解决的。

Some naming schemes use a more restricted multiple lookup method. For example, rather than allowing an arbitrary list of contexts, a naming scheme may require that contexts be arranged in nested layers. Whenever a resolution returns not-found in some layer, the resolver retries in the enclosing layer. Layered contexts were at one time popular in programming languages, where programs define and call on subprograms, because it can be convenient (to the point of being undisciplined, which is why it is no longer so popular) to allow a subprogram access by name to the variables of the defining or calling program. For another example, the scheme for numbering Internet network attachment points has an outer public layer and an inner private layer. Certain Internet address ranges (e.g., all addresses with a first byte of 10) are reserved for use in private networks; those address ranges constitute an inner private layer. These network addresses may be bound to different network attachment points in different private contexts without risk of conflict. Internet addresses that are outside the ranges reserved for private contexts should not be bound in any private context; they are instead resolved in the public context.

在一组分层上下文中，名称的范围是名称绑定到同一对象的层的范围。 仅绑定在最外层且始终绑定到同一对象（与当前上下文层无关）的名称称为全局名称。 解析全局名称的最外层是通用名称空间的一个示例。

In a set of layered contexts, the scope of a name is the range of layers in which the name is bound to the same object. A name that is bound only in the outermost layer, and is always bound to the same object, independent of the current context layer, is known as a global name. The outermost layer that resolves global names is an example of a universal name space.

顺便说一句，我们现在将术语“路径”用作形容词限定词和名词，但含义截然不同。路径名是带有其自身明确上下文的名称，而搜索路径是由上下文列表组成的上下文。因此，搜索路径的每个元素都可以是路径名。

Incidentally, we have now used the term path as both an adjective qualifier and a noun, but with quite different meanings. A path name is a name that carries its own explicit context, while a search path is a context that consists of a list of contexts. Thus each element of a search path may be a path name.

“搜索”一词还有另一个相关但略有不同的含义。Google 和 AltaVista 等互联网搜索引擎将由一个或多个关键词组成的查询作为输入，并返回包含这些关键词的万维网页面列表。多个结果（称为“命中”）是常见情况，例如，Google 实施了一个复杂的系统来对命中进行排名。Google 还为用户提供了仅接收排名最高的命中（“我很幸运”）或接收按排名排序的命中列表的选择。大多数现代台式计算机系统还提供某种形式的本地文件关键词搜索。当遇到不合格的“搜索”一词时，最好停下来弄清楚它是指多重查找还是关键词查询。

The word “search” also has another, related but somewhat different, meaning. Internet search engines such as Google and AltaVista take as input a query consisting of one or more key words, and they return a list of World Wide Web pages that contain those key words. Multiple results (known as “hits”) are the common case, and Google, for example, implements a sophisticated system for ranking the hits. Google also offers the user the choice of receiving just the highest-ranked hit (“I’m feeling lucky”) or receiving a rank-ordered list of hits. Most modern desktop computer systems also provide some form of key word search for local files. When one encounters the unqualified word “search”, it is a good idea to pause and figure out whether it refers to multiple lookup or to key word query.

2.2.5. 比较名称

2.2.5. Comparing Names

如前所述，有时还会对名称应用另一个操作：

As mentioned earlier, one more operation is sometimes applied to names:

结果←比较（名称1，名称2）

result ← COMPARE(name1, name2)

其中result是一个二进制值，TRUE或FALSE。名称比较的含义需要一些思考，因为调用者可能会想到三个不同的问题之一：

where result is a binary value, TRUE or FALSE. The meaning of name comparison requires some thought because the invoker might have one of three different questions in mind:

从机制上讲，第一个问题最容易回答，因为它只涉及比较两个名称的表示（“Jim Smith 和 Jim Smith 一样吗？”），而这正是名称解析器在表查找上下文中查找内容时所做的：在上下文中查找与要解析的名称相同的名称。另一方面，在许多情况下，答案是无用的，因为同一个名称可能在不同上下文中绑定到不同的值，而两个不同的名称可能是绑定到相同值的同义词。从第一个问题中可以了解到的只是名称字符串是否具有相同的位模式。

The first question is mechanically easiest to answer because it simply involves comparing the representations of the two names (“Is Jim Smith the same as Jim Smith?”), and it is exactly what a name resolver does when it looks things up in a table-lookup context: look through the context for a name that is the same as the one being resolved. On the other hand, in many situations the answer is not useful, since the same name may be bound to different values in different contexts and two different names may be synonyms that are bound to the same value. All one learns from the first question is whether or not the name strings have the same bit pattern.

因此，第二个问题的答案通常更有趣。（“刚刚获得诺贝尔奖的 Jim Smith 和我高中时认识的 Jim Smith 是同一个人吗？”）要获得该答案，需要将两个名称的上下文作为附加参数提供给COMPARE，以便它可以解析名称并比较结果。因此，例如，解析变量名A和变量名B可能会发现它们都绑定到相同的存储单元地址。即使是这个答案可能仍然没有揭示出预期的那么多信息，因为这两个名称可能解析为不同的下层命名方案的两个名称，在这种情况下，需要递归地询问有关下层名称的相同问题。例如，变量名A和B可能绑定到不同的存储单元地址，但如果正在使用虚拟内存，那么不同的虚拟存储单元地址可能会映射到相同的物理单元地址。（当我们读到第 5 章时，这个例子会更有意义。）

For that reason, the answer to the second question is often more interesting. (“Is the Jim Smith who just received the Nobel prize the same Jim Smith I knew in high school?”) Getting that answer requires supplying the contexts for the two names as additional arguments to COMPARE, so that it can resolve the names and compare the results. Thus, for example, resolving the variable name A and the variable name B may reveal that they are both bound to the same storage cell address. Even this answer may still not reveal as much as expected because the two names may resolve to two names of a different, lower-layer naming scheme, in which case the same questions need to be asked recursively about the lower-layer names. For example, variable names A and B may be bound to different storage cell addresses, but if a virtual memory is in use those different virtual storage cell addresses might map to the same physical cell address. (This example will make more sense when we reach Chapter 5.)

即使在到达该递归的底部之后，结果也可能是两个包含相同数据副本的不同物理存储容器的名称，或者可能是同一存储容器的两个不同的底层名称（即同义词）。（“关于 Jim Smith 的这个传记文件与关于 Jim Smith 的那个传记文件相同。是一份还是两份传记文件？”“关于 Edwin Aldrin 的这个传记与关于 Buzz Aldrin 的那个传记相同。这两个名字是同一个人的吗？”）因此出现了第三个问题，同时需要理解“相同”的含义。除非对底层物理表示有特定的理解，否则区分这两种情况的唯一方法可能是更改其中一个命名存储容器的内容，看看这是否会导致另一个内容发生变化。（“踢这个，看看那个会不会发出吱吱声。”）

Even after reaching the bottom of that recursion, the result may be the names of two different physical storage containers that contain identical copies of data, or it may be two different lower-layer names (that is, synonyms) for the same storage container. (“This biography file on Jim Smith is identical to that biography file on Jim Smith. Are there one or two biography files?” “This biography about Edwin Aldrin is identical to that biography about Buzz Aldrin. Are those two names for the same person?”) Thus the third question arises, along with a need to understand what it means to be the “same”. Unless one has some specific understanding of the underlying physical representation, the only way to distinguish the two cases may be to change the contents of one of the named storage containers and see if that causes the contents of the other one to change. (“Kick this one and see if that one squeals.”)

实际上，系统（和一些编程语言）通常提供几个具有不同语义的COMPARE运算符，旨在帮助回答这些不同的问题，程序员或用户必须了解哪种COMPARE操作适合当前任务。例如，LISP 语言提供了三个比较运算符，名为EQ（比较其命名参数的绑定）、EQU（比较其命名参数的值）和EQUALS（递归比较整个数据结构）。

In practice, systems (and some programming languages) typically provide several COMPARE operators that have different semantics designed to help answer these different questions, and the programmer or user must understand which COMPARE operation is appropriate for the task at hand. For example, the LISP language provides three comparison operators, named EQ (which compares the bindings of its named arguments), EQU (which compares the values of its named arguments), and EQUALS (which recursively compares entire data structures.)

2.2.6. 名称发现

2.2.6. Name Discovery

所有名称引用的底层都是一个递归协议，它回答了“您如何知道要使用这个名称？”这个问题。这个名称发现协议会将对象导出的名称告知对象的潜在用户。名称发现涉及两个基本要素：导出器宣传名称的存在，而潜在用户则搜索合适的广告。名称发现之所以具有递归性，是因为名称用户必须首先知道要搜索广告的地方的名称。这个递归必须在某个地方终止，也许是在某个名称用户和某个名称导出器之间的直接、计算机外的通信中。

Underlying all name reference is a recursive protocol that answers the question, “How did you know to use this name?” This name discovery protocol informs an object’s prospective user of the name that the object exports. Name discovery involves two basic elements: the exporter advertises the existence of the name, while the prospective user searches for an appropriate advertisement. The thing that makes name discovery recursive is that the name user must first know the name of a place to search for the advertisement. This recursion must terminate somewhere, perhaps in a direct, outside-the-computer communication between some name user and some name exporter.

最简单的情况是，一个程序员编写了一个由两个过程组成的程序，其中一个过程通过名称引用另一个过程。由于这两个过程是同一个程序员编写的，因此名称发现是明确的，不需要递归。接下来，假设这两个程序是由两个不同的程序员编写的。想要按名称使用过程的程序员必须以某种方式发现导出的名称。一种可能性是，第二个程序员通过在走廊里大声喊出过程的名称来执行广告。另一种可能性是，使用程序的程序员在每个人都同意放置共享过程的共享目录中查找。该程序员如何知道该共享目录的名称？也许有人在走廊里大声喊出了这个名字。或者，它可能是一个标准库目录，其名称列在程序员的参考手册中，在这种情况下，该手册终止递归协议。虽然程序库名称通常不会出现在杂志广告或广告牌上，但在这些地方发现万维网站点的名称已变得很常见。名称发现可以采取多种形式：

The simplest case is a programmer who writes a program consisting of two procedures, one of which refers to the other by name. Since the same programmer wrote both, name discovery is explicit and no recursion is necessary. Next, suppose the two programs are written by two different programmers. The programmer who wants to use a procedure by name must somehow discover the exported name. One possibility is that the second programmer performs the advertisement by shouting the procedure’s name down the hall. Another possibility is that the using programmer looks in a shared directory in which everyone agrees to place shared procedures. How does that programmer know the name of that shared directory? Perhaps someone shouted that name down the hall. Or perhaps it is a standard library directory whose name is listed in the programmers’ reference manual, in which case that manual terminates the recursive protocol. Although program library names don’t usually appear in magazine advertisements or on billboards, it has become commonplace to discover the name of a World Wide Web site in such places. Name discovery can take several forms:

上述任何一种名称发现方法都可能需要首先发现其他名称，例如知名名称的参考源的名称、发布广播的公告板的名称、名称解析器的名称、聚会主持人的名称等等。发现这个其他名称的方法可能与第一次调用的方法相同，也可能不同。设计人员必须牢记的重要一点是，递归必须在某处终止 — 它不能是循环的。

Any of the above methods of name discovery may require first discovering some other name, such as the name of the reference source for well-known names, the name of the bulletin board on which broadcasts are placed, the name of the name resolver, the name of the party host, and so on. The method of discovering this other name may be the same as the method first invoked, or it may be different. The important thing the designer must keep in mind is that the recursion must terminate somewhere—it can’t be circular.

需要名称的地方都需要某种名称发现方法。一个有趣的练习是分析本章前面部分提到的一些名称示例，跟踪名称发现递归以查看其如何终止，因为在许多情况下，终止与名称使用和解析事件相距甚远，以至于早已被遗忘。后面的章节将介绍许多其他名称发现示例：用于客户端和服务的名称，其中客户端需要发现适当服务的名称；数据通信网络，其中路由提供了一个特别明确的名称发现示例；以及安全性，其中确定终止步骤的完整性至关重要。

Some method of name discovery is required wherever a name is needed. An interesting exercise is to analyze some of the examples of names mentioned in earlier parts of this chapter, tracing the name discovery recursion to see how it terminates, because in many cases that termination is so distant from the event of name usage and resolution that it has long since been forgotten. Many additional examples of name discovery will show up in later chapters: names used for clients and services, where a client needs to discover the name of an appropriate service; data communication networks, where routing provides a particularly explicit example of name discovery; and security, where it is critical to establish the integrity of the terminating step.

2.3.1. 硬件层：总线

2.3.1. A Hardware Layer: The Bus

典型计算机的硬件层由直接实现三个基本抽象的低级版本的模块构成。在图 2.17的示例中，处理器模块解释程序，随机存取存储器模块存储程序和数据，输入/输出 (I/O) 模块实现与计算机外部世界的通信链接。

The hardware layer of a typical computer is constructed of modules that directly implement low-level versions of the three fundamental abstractions. In the example of Figure 2.17, the processor modules interpret programs, the random access memory modules store both programs and data, and the input/output (I/O) modules implement communication links to the world outside the computer.

图 2.17一台计算机，其中有多个模块通过共享总线连接。数字是所连接模块响应的总线地址。

Figure 2.17 A computer with several modules connected by a shared bus. The numbers are the bus addresses to which the attached module responds.

每种硬件模块可能都有若干个示例 — — 多个处理器（可能一个芯片上有若干个处理器，这个组织的名称叫作多核）、多个内存以及若干种 I/O 模块。仔细检查后会发现，I/O 模块实际上是实现 I/O 程序的专用解释器。因此，磁盘控制器就是磁盘 I/O 程序的解释器。它的职责包括将磁盘地址映射到磁道和扇区号，以及将数据从磁盘移动到内存。网络控制器是一种解释器，它在另一端与一个或多个实际通信链路进行通信。显示控制器解释它在内存中找到的显示列表，并在显示过程中点亮显示屏上的像素。键盘控制器解释键击并将结果放入内存。时钟可能只是一个微型解释器，它不断用一天中的时间更新一个寄存器。

There may be several examples of each kind of hardware module—multiple processors (perhaps several on one chip, an organization that goes by the buzzword name multicore), multiple memories, and several kinds of I/O modules. On closer inspection the I/O modules turn out to be specialized interpreters that implement I/O programs. Thus, the disk controller is an interpreter of disk I/O programs. Among its duties are mapping disk addresses to track and sector numbers and moving data from the disk to the memory. The network controller is an interpreter that talks on its other side to one or more real communication links. The display controller interprets display lists that it finds in memory, lighting pixels on the display as it goes. The keyboard controller interprets keystrokes and places the result in memory. The clock may be nothing but a minuscule interpreter that continually updates a single register with the time of day.

各种模块插入共享总线，这是一种高度专业化的通信链路，用于向其他模块发送消息。总线设计多种多样，但它们有一些共同的特征。其中一个共同特征是一组由地址^线、数据线和控制线组成的线路，它们连接到每个模块上的总线接口。由于总线是共享的，因此第二个共同特征是一组规则，称为总线仲裁协议，用于决定哪个模块可以在任何特定时间发送或接收消息。一些总线有一个附加模块，即总线仲裁器，它是一个电路或一个微型解释器，用于选择几个竞争模块中的哪个可以使用总线。在其他设计中，总线仲裁是分布在总线接口之间的一项功能。正如总线设计多种多样一样，总线仲裁协议也多种多样。一个特别有影响力的总线示例是 UNIBUS® ^{，由 Digital Equipment Corporation 在 20 世纪 70 年代推出。共享总线和标准仲裁协议提供的模块化有助于重塑计算机行业，如}边栏 1.5中所述。

The various modules plug into the shared bus, which is a highly specialized communication link used to SEND messages to other modules. There are numerous bus designs, but they have some common features. One such common feature is a set of wires^* comprising address, data, and control lines that connect to a bus interface on each module. Because the bus is shared, a second common feature is a set of rules, called the bus arbitration protocol, for deciding which module may send or receive a message at any particular time. Some buses have an additional module, the bus arbiter, a circuit or a tiny interpreter that chooses which of several competing modules can use the bus. In other designs, bus arbitration is a function distributed among the bus interfaces. Just as there are many bus designs, there are also many bus arbitration protocols. A particularly influential example of a bus is the UNIBUS^®, introduced in the 1970s by Digital Equipment Corporation. The modularity provided by a shared bus with a standard arbitration protocol helped to reshape the computer industry, as was described in Sidebar 1.5.

总线设计的第三个共同特征是总线是一种广播链路，这意味着连接到总线的每个模块都会听到每条消息。由于大多数消息实际上只发送给一个模块，因此消息中称为总线地址的字段标识了预期的接收者。每个模块的总线接口配置为响应特定的一组总线地址。每个模块检查每条消息的总线地址字段（在并行总线中，通常由一组与消息其余部分分开的线路传输）并忽略任何不是发送给它的消息。因此，总线地址定义了一个地址空间。图 2.17显示两个处理器可能分别在总线地址 101 和 102 接受消息；显示控制器在总线地址 103 接受消息；磁盘控制器在总线地址 104 和 105 接受消息（使用两个地址可以方便区分对其两个磁盘的请求）；网络在总线地址 106 接受消息；键盘在总线地址 107 接受消息；时钟位于总线地址 109。为了提高速度，内存模块通常配置一系列总线地址，每个内存地址一个总线地址。因此，如果图 2.17中的两个内存模块各自实现 1,024 个内存地址的地址空间，则它们可能分别配置总线地址 1024–2047 和 3072–4095。^*

A third common feature of bus designs is that a bus is a broadcast link, which means that every module attached to the bus hears every message. Since most messages are actually intended for just one module, a field of the message called the bus address identifies the intended recipient. The bus interface of each module is configured to respond to a particular set of bus addresses. Each module examines the bus address field (which in a parallel bus is usually carried on a set of wires separate from the rest of the message) of every message and ignores any message not intended for it. The bus addresses thus define an address space. Figure 2.17 shows that the two processors might accept messages at bus addresses 101 and 102, respectively; the display controller at bus address 103; the disk controller at bus addresses 104 and 105 (using two addresses makes it convenient to distinguish requests for its two disks); the network at bus address 106; the keyboard at bus address 107; and the clock at bus address 109. For speed, memory modules typically are configured with a range of bus addresses, one bus address per memory address. Thus, if in Figure 2.17 the two memory modules each implement an address space of 1,024 memory addresses, they might be configured with bus addresses 1024–2047 and 3072–4095, respectively.^*

任何希望通过总线发送消息的总线模块都必须知道预期接收者配置为接受的总线地址。某些总线中的名称发现非常简单：设置系统的人会将总线地址的知识明确配置到处理器软件中，然后该软件会通过总线发送的消息将此知识传递给其他模块。其他总线设计会在模块插入总线并宣布其存在时动态分配总线地址。

Any bus module that wishes to send a message over the bus must know a bus address that the intended recipient is configured to accept. Name discovery in some buses is quite simple: whoever sets up the system explicitly configures the knowledge of bus addresses into the processor software, and that software passes this knowledge along to other modules in messages it sends over the bus. Other bus designs dynamically assign bus addresses to modules as they are plugged in to the bus and announce their presence.

一种常见的总线设计称为拆分事务。在这种设计中，当一个模块想要与另一个模块通信时，第一个模块使用控制线上的总线仲裁协议来请求独占使用总线来发送消息。获得独占使用权后，模块会将目标模块的总线地址放在地址线上，将消息的剩余部分放在数据线上。假设在设计中，总线和连接到总线的模块以不协调的时钟运行（即，它们是异步的），然后它会在其中一条控制线上发出信号（称为READY），提醒其他模块总线上有消息。当接收模块注意到它的一个地址在总线的地址线上时，它会将该地址和数据线上的其余消息复制到其本地寄存器中，并在另一条控制线上发出信号（称为ACKNOWLEDGE）告诉发送者可以安全地释放总线，以便其他模块可以使用它。 （如果总线和模块都使用公共时钟运行，则不需要READY和ACKNOWLEDGE线；相反，每个模块在每个时钟周期检查地址线。）然后，接收器检查地址和消息并执行请求的操作，这可能涉及将一个或多个消息发送回原始请求模块，或者在某些情况下，甚至发送回其他模块。

A common bus design is known as split-transaction. In this design, when one module wants to communicate with another, the first module uses the bus arbitration protocol on the control wires to request exclusive use of the bus for a message. Once it has that exclusive use, the module places a bus address of the destination module on the address wires and the remainder of the message on the data wires. Assuming a design in which the bus and the modules attached to it run on uncoordinated clocks (that is, they are asynchronous), it then signals on one of the control wires (called READY) to alert the other modules that there is a message on the bus. When the receiving module notices that one of its addresses is on the address lines of the bus, it copies that address and the rest of the message on the data wires into its local registers and signals on another control line (called ACKNOWLEDGE) to tell the sender that it is safe to release the bus so that other modules can use it. (If the bus and the modules are all running with a common clock, the READY and ACKNOWLEDGE lines are not needed; instead, each module checks the address lines on each clock cycle.) Then, the receiver inspects the address and message and performs the requested operation, which may involve sending one or more messages back to the original requesting module or, in some cases, even to other modules.

例如，假设处理器 #2 在解释正在运行的应用程序时遇到指令

For example, suppose that processor #2, while interpreting a running application program, encounters the instruction

加载1742，R1

LOAD 1742, R1

意思是“将内存地址 1742 的内容加载到处理器寄存器 R1 中”。在最简单的方案中，处理器只是将其在指令中找到的地址直接转换为总线地址，而不做任何更改。因此，它通过总线发送此消息：

which means “load the contents of memory address 1742 into processor register R1”. In the simplest scheme, the processor just translates addresses it finds in instructions directly to bus addresses without change. It thus sends this message across the bus:

处理器#2 ⇒所有总线模块: {1742, READ , 102}

processor #2 ⇒ all bus modules: {1742, READ, 102}

该消息包含三个字段。第一个消息字段(1742)是内存 #1 响应的总线地址之一；第二个消息字段请求接收方执行读取操作；第三个消息字段指示接收方应使用总线地址102通过总线将结果值发回。每个内存模块识别的内存地址基于 2 的幂，因此内存模块只需检查几个高位地址位即可识别其自身范围内的所有地址。在这种情况下，总线地址在内存模块 1 识别的范围内，因此该模块通过将消息复制到其自己的寄存器中进行响应。它确认请求，处理器释放总线，然后内存模块执行内部操作

The message contains three fields. The first message field (1742) is one of the bus addresses to which memory #1 responds; the second message field requests the recipient to perform a READ operation; and the third indicates that the recipient should send the resulting value back across the bus, using the bus address 102. The memory addresses recognized by each memory module are based on powers of two, so the memory modules can recognize all of the addresses in their own range by examining just a few high-order address bits. In this case, the bus address is within the range recognized by memory module 1, so that module responds by copying the message into its own registers. It acknowledges the request, the processor releases the bus, and the memory module then performs the internal operation

值←读( 1742 )

value ← READ (1742)

有了值之后，内存模块现在自己获取总线，并通过执行总线操作将结果发送回处理器 #2

With value in hand, the memory module now itself acquires the bus and sends the result back to processor #2 by performing the bus operation

内存#1 ⇒所有总线模块: {102,值}

memory #1 ⇒ all bus modules: {102, value}

其中102是原始READ请求消息中提供的处理器总线地址。处理器可能正在等待此结果，它注意到总线地址线现在包含其自己的总线地址 102。因此，它将数据线中的值复制到其寄存器 R1 中，作为原始程序指令的请求。它确认收到消息，内存模块释放总线以供其他模块使用。

where 102 is the bus address of the processor as supplied in the original READ request message. The processor, which is probably waiting for this result, notices that the bus address lines now contain its own bus address 102. It therefore copies the value from the data lines into its register R1, as the original program instruction requested. It acknowledges receipt of the message, and the memory module releases the bus for use by other modules.

简单的 I/O 设备（如键盘）以类似的方式运行。在系统初始化时，其中一个处理器向键盘控制器发送一条消息，告诉它将所有击键发送到该处理器。每次用户按下一个键时，键盘控制器都会向处理器发送一条消息，其中包含按下的键的名称作为数据。在这种情况下，处理器可能没有等待此消息，但其总线接口（实际上是与处理器同时运行的单独解释器）注意到出现了一条带有其总线地址的消息。总线接口将数据从总线复制到临时寄存器，确认该消息，并向处理器发送信号，使处理器在下一个指令周期执行中断。然后，中断处理程序将数据从临时寄存器传输到保存键盘输入的某个位置，可能是通过总线向其中一个内存模块发送另一条消息。

Simple I/O devices, such as keyboards, operate in a similar fashion. At system initialization time, one of the processors SENDs a message to the keyboard controller telling it to SEND all keystrokes to that processor. Each time that the user depresses a key, the keyboard controller SENDs a message to the processor containing as data the name of the key that was depressed. In this case, the processor is probably not waiting for this message, but its bus interface (which is in effect a separate interpreter running concurrently with the processor) notices that a message with its bus address has appeared. The bus interface copies the data from the bus into a temporary register, acknowledges the message, and sends a signal to the processor that will cause the processor to perform an interrupt on its next instruction cycle. The interrupt handler then transfers the data from the temporary register to some place that holds keyboard input, perhaps by SENDing yet another message over the bus to one of the memory modules.

这种设计的一个潜在问题是，中断处理程序必须在键盘处理程序发送另一条击键消息之前响应并从临时寄存器中读取击键数据。由于键盘打字速度与计算机速度相比较慢，因此中断处理程序很有可能及时读取数据，以免下一次击键覆盖数据。但是，硬盘等速度更快的设备可能会覆盖临时寄存器。一种解决方案是编写一个在紧密循环中运行的处理器程序，等待磁盘控制器通过总线发送的数据，并立即通过总线将该数据再次发送至内存模块。

One potential problem of this design is that the interrupt handler must respond and read the keystroke data from the temporary register before the keyboard handler SENDs another keystroke message. Since keyboard typing is slow compared with computer speeds, there is a good chance that the interrupt handler will be there in time to read the data before the next keystroke overwrites it. However, faster devices such as a hard disk might overwrite the temporary register. One solution would be to write a processor program that runs in a tight loop, waiting for data that the disk controller sends over the bus and immediately SENDing that data again over the bus to a memory module.

一些低端计算机设计确实做到了这一点，但设计人员可以通过升级磁盘控制器以使用称为直接内存访问（DMA）的技术来获得更高的性能。使用这种技术，当处理器向磁盘控制器发送请求以从磁盘读取数据块时，它会将内存中缓冲区的地址作为请求消息的字段。然后，当数据从磁盘流入时，磁盘控制器将其直接发送到内存模块，并在发送之间适当增加内存地址。除了减轻处理器的负载外，DMA 还减少了共享总线的负载，因为它只将每块数据传输到总线一次（从磁盘控制器到内存），而不是两次（首先从磁盘控制器到处理器，然后从处理器到内存）。此外，如果总线允许长消息，DMA 控制器可能能够比处理器更好地利用该功能，处理器通常设计为以与其自己的寄存器大小相同的单位发送和接收总线数据。通过发送较长的消息，DMA 控制器可以提高性能，因为它可以分摊总线仲裁协议的开销，而总线仲裁协议必须每条消息执行一次。最后，DMA 允许处理器在磁盘控制器传输数据的同时执行其他程序。由于并发操作可以隐藏磁盘传输的延迟，因此它可以提供额外的性能增强。第6 章将进一步讨论通过隐藏延迟来提高性能的想法。

Some low-end computer designs do exactly that, but a designer can obtain substantially higher performance by upgrading the disk controller to use a technique called direct memory access, or DMA. With this technique, when a processor SENDs a request to a disk controller to READ a block of data from the disk, it includes the address of a buffer in memory as a field of the request message. Then, as data streams in from the disk, the disk controller SENDs it directly to the memory module, incrementing the memory address appropriately between SENDs. In addition to relieving the load on the processor, DMA also reduces the load on the shared bus because it transfers each piece of data across the bus just once (from the disk controller to the memory) rather than twice (first from the disk controller to the processor and then from the processor to the memory). Also, if the bus allows long messages, the DMA controller may be able to take better advantage of that feature than the processor, which is usually designed to SEND and RECEIVE bus data in units that are the same size as its own registers. By SENDing longer messages, the DMA controller increases performance because it amortizes the overhead of the bus arbitration protocol, which it must perform once per message. Finally, DMA allows the processor to execute some other program at the same time that the disk controller is transferring data. Because concurrent operation can hide the latency of the disk transfer, it can provide an additional performance enhancement. The idea of enhancing performance by hiding latency is discussed further in Chapter 6.

一种方便的 I/O 和其他总线连接模块接口是将总线地址分配给模块的控制寄存器和缓冲区。由于每个处理器将总线地址直接映射到其自己的内存地址空间，因此在处理器中执行的LOAD和STORE指令实际上可以寻址 I/O 模块的寄存器和缓冲区，就好像它们是内存中的位置一样。该技术称为内存映射 I/O。

A convenient interface to I/O and other bus-attached modules is to assign bus addresses to the control registers and buffers of the module. Since each processor maps bus addresses directly into its own memory address space, LOAD and STORE instructions executed in the processor can in effect address the registers and buffers of the I/O module as if they were locations in memory. The technique is known as memory-mapped I/O.

内存映射 I/O 可以与 DMA 结合使用。例如，假设为内存映射 I/O 设计的磁盘控制器将总线地址分配给其四个控制寄存器，如下所示：

Memory-mapped I/O can be combined with DMA. For example, suppose that a disk controller designed for memory-mapped I/O assigns bus addresses to four of its control registers as follows:

总线地址控制寄存器

bus address control register

121 扇区编号

121 sector_number

122 DMA_起始地址

122 DMA_start_address

123 DMA_计数

123 DMA_count

124 控制

124 control

要执行磁盘 I/O，处理器使用STORE指令将适当的初始化值发送到前三个磁盘控制器寄存器，并使用最后的STORE指令发送一个值，该值设置控制寄存器中的某个位，磁盘控制器会将该位解释为启动信号。程序要获取当前存储在扇区号 11742 的 256 字节磁盘扇区，并将数据传输到从位置 3328 开始的内存中，首先用这些值加载四个寄存器，然后将寄存器的STORE发送到相应的总线地址：

To do disk I/O, the processor uses STORE instructions to SEND appropriate initialization values to the first three disk controller registers and a final STORE instruction to SEND a value that sets a bit in the control register that the disk controller interprets as the signal to start. A program to GET a 256-byte disk sector currently stored at sector number 11742 and transfer the data into memory starting at location 3328 starts by loading four registers with these values and then issuing STOREs of the registers to the appropriate bus addresses:

R1 ←11742； R2←3328； R3←256； R4←1；

R1 ← 11742; R2 ← 3328; R3 ← 256; R4 ← 1;

STORE 121,R1 //设置扇区号

STORE 121,R1       // set sector number

STORE 122,R2 //设置内存地址寄存器

STORE 122,R2       // set memory address register

STORE 123,R3 //设置字节数

STORE 123,R3       // set byte count

STORE 124,R4 //启动磁盘控制器运行

STORE 124,R4       // start disk controller running

在完成由上一条STORE指令生成的总线SEND后，之前处于空闲状态的磁盘控制器将立即开始工作，将请求的扇区从磁盘读入内部缓冲区，并开始使用 DMA 将缓冲区的内容一次一个块地传输到内存中。如果总线可以处理长度为 8 字节的块，则磁盘控制器将发送一系列总线消息，例如

Upon completion of the bus SEND generated by the last STORE instruction, the disk controller, which was previously idle, leaps into action, reads the requested sector from the disk into an internal buffer, and begins using DMA to transfer the contents of the buffer to memory one block at a time. If the bus can handle blocks that are 8 bytes long, the disk controller would SEND a series of bus messages such as

磁盘控制器 #1 ⇒所有总线模块:{3328，块[1]}

disk controller #1 ⇒ all bus modules:{3328, block[1]}

磁盘控制器 #1 ⇒所有总线模块:{3336，块[2]}

disk controller #1 ⇒ all bus modules:{3336, block[2]}

ETC …

etc …

内存映射 I/O 是一种流行的接口，因为它为每个实现它的总线模块提供了统一的类似内存的LOAD和STORE接口。另一方面，设计人员在尝试过度扩展内存映射模型时必须谨慎。例如，在具有 32 位地址空间的系统中，尝试安排处理器可以直接寻址磁盘上的单个字节或字可能会出现问题，因为小到 4 GB 的磁盘会占用整个地址空间。更重要的是，与处理器的周期时间相比，磁盘的延迟非常大。对于 STORE 指令，有时在几纳秒内完成（当地址在电子内存中时），有时需要 10 毫秒才能完成（当地址在磁盘上时），这将是非常出乎意料的，并且会使编写具有可预测性能的程序变得困难。此外，它还会违反人类工程学的基本规则，即最小惊讶原则（参见边栏 2.5）。最重要的是，磁盘的物理特性使得 DMA 访问模型比内存映射 I/O 模型更合适。

Memory-mapped I/O is a popular interface because it provides a uniform memory-like LOAD and STORE interface to every bus module that implements it. On the other hand, the designer must be cautious in trying to extend the memory-mapped model too far. For example, trying to arrange so the processor can directly address individual bytes or words on a magnetic disk could be problematic in a system with a 32-bit address space because a disk as small as 4 gigabytes would use up the entire address space. More important, the latency of a disk is extremely large compared with the cycle time of a processor. For the STORE instruction to sometimes operate in a few nanoseconds (when the address is in electronic memory) and other times require 10 milliseconds to complete (when the address is on the disk) would be quite unexpected and would make it difficult to write programs that have predictable performance. In addition, it would violate a fundamental rule of human engineering, the principle of least astonishment (see Sidebar 2.5). The bottom line is that the physical properties of the magnetic disk make the DMA access model more appropriate than the memory-mapped I/O model.

2.3.2. 软件层：文件抽象

2.3.2. A Software Layer: The File Abstraction

计算机系统的中层和高层通常以软件模块的形式实现。为了使这种分层组织具体化，请考虑文件，它是内存抽象的高级版本。文件包含位或字节数组，其数量由应用程序选择。文件具有两个关键属性：

The middle and higher layers of a computer system are usually implemented as software modules. To make this layered organization concrete, consider the file, a high-level version of the memory abstraction. A file holds an array of bits or bytes, the number of which the application chooses. A file has two key properties:

综合起来，这两个特性意味着，如果 Alice 创建了一个名为“战略计划”的新文件，在其中写入了一些信息，关闭计算机，第二天再次打开计算机，她将能够读取名为“战略计划”的文件并取回其内容。此外，她可以告诉 Bob 查看名为“战略计划”的文件。当 Bob 要求系统读取同名文件时，他将读取她创建的文件。大多数文件系统还为文件提供其他附加属性，如时间戳（用于确定文件的创建、最后修改或最后使用时间）、文件持久性的保证（第 10 章 [在线] 重新讨论的主题）以及控制谁可以共享文件的能力（第 11 章 [在线] 的主题之一）。

Taken together, these two features mean that if, for example, Alice creates a new file named “strategic plan”, WRITEs some information in it, shuts down the computer, and the next day turns it on again, she will then be able to READ the file named “strategic plan” and get back its content. Furthermore, she can tell Bob to look at the file named “strategic plan”. When Bob asks the system to READ a file with that name, he will read the file that she created. Most file systems also provide other additional properties for files, such as timestamps to determine when they were created, last modified, or last used, assurances about their durability (a topic that Chapter 10 [on-line] revisits), and the ability to control who may share them (one of the topics of Chapter 11 [on-line]).

系统层使用硬件层的模块来实现文件。图 2.18显示了一个简单的应用程序的伪代码，它从键盘设备读取输入，将该输入写入文件，并将其显示在显示设备上。

The system layer implements files using modules from the hardware layer. Figure 2.18 shows the pseudocode of a simple application that reads input from a keyboard device, writes that input to a file, and also displays it on the display device.

图 2.18使用文件抽象实现显示程序，该程序还将键盘输入写入文件中。为清楚起见，此程序忽略了任何抽象文件原语可能返回错误状态的可能性。

Figure 2.18 Using the file abstraction to implement a display program, which also writes the keyboard input in a file. For clarity, this program ignores the possibility that any of the abstract file primitives may return an error status.

文件抽象的典型 API 包含对OPEN文件、READ和WRITE文件部分以及CLOSE文件的调用。OPEN调用将文件名转换为本地名称空间中的临时名称，以供READ和WRITE操作使用。此外，OPEN通常会检查是否允许此用户访问该文件。作为最后一步，OPEN将游标（有时称为文件指针）设置为零。游标记录从文件开头的偏移量，用作READ和WRITE的起点。某些文件系统设计为READ和WRITE提供了单独的游标，在这种情况下OPEN可能会将WRITE游标初始化为文件中的字节数。

A typical API for the file abstraction contains calls to OPEN a file, to READ and WRITE parts of the file, and to CLOSE the file. The OPEN call translates the file name into a temporary name in a local name space to be used by the READ and WRITE operations. Also, OPEN usually checks whether this user is permitted access to the file. As its last step, OPEN sets a cursor, sometimes called a file pointer, to zero. The cursor records an offset from the beginning of the file to be used as the starting point for READs and WRITEs. Some file system designs provide a separate cursor for READs and WRITEs, in which case OPEN may initialize the WRITE cursor to the number of bytes in the file.

调用READ会将文件中指定数量的字节传递给调用者，从READ游标开始。它还会将读取的字节数添加到READ游标中，以便下一个READ可以从上一个READ停止的地方继续。如果程序要求读取文件末尾以外的字节，READ将返回某种文件末尾状态指示符。

A call to READ delivers to the caller a specified number of bytes from the file, starting from the READ cursor. It also adds to the READ cursor the number of bytes read so that the next READ proceeds where the previous READ left off. If the program asks to read bytes beyond the end of the file, READ returns some kind of end-of-file status indicator.

类似地，WRITE操作将一个包含字节和长度的缓冲区作为参数，将这些字节存储在文件中，从WRITE光标指示的偏移量开始（如果WRITE光标从文件末尾开始或到达文件末尾，WRITE通常意味着扩展文件的大小），并将写入的字节数添加到WRITE光标，以便下一个WRITE可以从那里继续。如果设备上没有足够的空间来写入那么多字节，WRITE过程将失败，并返回某种设备已满错误状态或异常。

Similarly, the WRITE operation takes as arguments a buffer with bytes and a length, stores those bytes in the file starting at the offset indicated by the WRITE cursor (if the WRITE cursor starts at or reaches the end of the file, WRITE usually implies extending the size of the file), and adds to the WRITE cursor the number of bytes written so that the next WRITE can continue from there. If there is not enough space on the device to write that many bytes, the WRITE procedure fails by returning some kind of device-full error status or exception.

最后，当程序完成读写操作后，它会调用CLOSE过程。CLOSE释放文件系统为文件维护的任何内部状态（例如，游标和临时文件名的记录，这些记录不再有意义）。某些文件系统还确保当CLOSE返回时，修改后的文件的所有部分都已持久存储在非易失性存储设备上。其他文件系统在CLOSE返回后在后台执行此操作。

Finally, when the program is finished reading and writing, it calls the CLOSE procedure. CLOSE frees up any internal state that the file system maintains for the file (for example, the cursors and the record of the temporary file name, which is no longer meaningful). Some file systems also ensure that, when CLOSE returns, all parts of the modified file have been stored durably on a non-volatile memory device. Other file systems perform this operation in the background after CLOSE returns.

文件系统模块通过将文件的字节映射到磁盘扇区来实现文件 API。对于每个文件，文件系统都会创建文件名称和存储文件的磁盘扇区的记录。文件系统还将此记录存储在磁盘上。当计算机重新启动时，文件系统必须以某种方式发现它留下这些记录的位置，以便再次找到文件。名称发现的典型过程是文件系统保留一个众所周知的磁盘扇区（例如扇区号 1），并使用该众所周知的磁盘扇区作为立足点来定位它留下其余文件系统信息的扇区。UNIX 文件系统 API 及其实现的详细描述在第2.5 节中。

The file system module implements the file API by mapping bytes of the file to disk sectors. For each file the file system creates a record of the name of the file and the disk sectors in which it has stored the file. The file system also stores this record on the disk. When the computer restarts, the file system must somehow discover the place where it left these records so that it can again find the files. A typical procedure for name discovery is for the file system to reserve one, well-known, disk sector such as sector number 1, and use that well-known disk sector as a toehold to locate the sectors where it left the rest of the file system information. A detailed description of the UNIX file system API and its implementation is in Section 2.5.

你也许会奇怪为什么文件 API除了支持READ和WRITE之外还支持OPEN和CLOSE；毕竟，你可以要求程序员在每次READ和WRITE调用时传递文件名和文件位置偏移量。原因是OPEN和CLOSE过程标记一系列相关READ和WRITE操作的开始和结束，以便文件系统知道哪些读写属于一个组。进行分组以及在分组中使用临时文件名有几个很好的理由。最初，性能和资源管理问题促使引入OPEN和CLOSE，但后来的接口实现利用了OPEN和CLOSE的存在，在并发文件访问和故障下提供清晰的语义。

One might wonder why the file API supports OPEN and CLOSE in addition to READ and WRITE; after all, one could ask the programmer to pass the file name and a file position offset on each READ and WRITE call. The reason is that the OPEN and CLOSE procedures mark the beginning and the end of a sequence of related READ and WRITE operations so that the file system knows which reads and writes belong together as a group. There are several good reasons for grouping and for the use of a temporary file name within the grouping. Originally, performance and resource management concerns motivated the introduction of OPEN and CLOSE, but later implementations of the interface exploited the existence of OPEN and CLOSE to provide clean semantics under concurrent file access and failures.

早期的文件系统引入了OPEN来分摊解析文件名的成本。文件名是可能包含多个部分的路径名。通过在OPEN上解析文件名一次并为结果赋予简单名称，READ和WRITE避免了在每次调用时解析名称。同样，OPEN可以分摊检查用户是否具有使用文件的适当权限的成本。

Early file systems introduced OPEN to amortize the cost of resolving a file name. A file name is a path name that may contain several components. By resolving the file name once on OPEN and giving the result a simple name, READ and WRITE avoid having to resolve the name on each invocation. Similarly, OPEN amortizes the cost of checking whether the user has the appropriate permissions to use the file.

引入CLOSE是为了简化资源管理：当应用程序调用CLOSE时，文件系统知道该应用程序不需要文件系统内部维护的资源（例如，光标）。即使第二个应用程序在第一个应用程序完成读写文件之前删除了文件，文件系统也可以合理地为第一个应用程序实现READ和WRITE过程（例如，只有在所有OPEN该文件的人都调用CLOSE之后，才丢弃文件的内容）。

CLOSE was introduced to simplify resource management: when an application invokes CLOSE, the file system knows that the application doesn’t need the resources (e.g., the cursor) that the file system maintains internally. Even if a second application removes a file before a first application is finished reading and writing the file, the file system can implement READ and WRITE procedures for the first application sensibly (for example, discard the contents of the file only after everyone that OPENed the file has called CLOSE).

较新的文件系统使用OPEN和CLOSE来标记原子操作的开始和结束。文件系统可以将所有中间的READ和WRITE调用视为单个不可分割的操作，即使在同时访问文件或系统崩溃（部分但不是全部WRITE已完成）的情况下也是如此。随之而来的是两个机会：

More recent file systems use OPEN and CLOSE to mark the beginning and end of an atomic action. The file system can treat all intervening READ and WRITE calls as a single indivisible operation, even in the face of concurrent access to the file or a system crash after some but not all of the WRITEs have completed. Two opportunities ensue:

OPEN / CLOSE模型是有代价的：文件系统必须以解析的文件名和游标的形式维护每个客户端的状态。可以设计一个完全无状态的文件接口。一个例子是网络文件系统，如第4.5 节所述。

There is a cost to the OPEN/CLOSE model: the file system must maintain per-client state in the form of the resolved file name and the cursor(s). It is possible to design a completely stateless file interface. An example is the Network File System, described in Section 4.5.

文件是一种非常方便的内存抽象，在某些系统（例如UNIX系统及​​其衍生系统）中，计算机系统中的每个输入/输出设备都提供文件接口（参见图 2.19）。在这样的系统中，文件不仅是非易失性存储器（例如磁盘）的抽象，而且还是键盘设备、显示器、通信链路等的便捷接口。在这样的系统中，每个 I/O 设备在文件命名方案中都有一个名称。程序OPEN键盘设备、从键盘设备READ字节，然后CLOSE键盘设备，而不必知道有关键盘管理过程的任何细节，例如键盘类型等。类似地，为了与显示器交互，程序可以OPEN显示设备、WRITE并CLOSE它。程序不需要知道有关显示器的任何细节。根据最小惊讶原则，每个设备管理过程为每种文件系统方法提供了一些合理的解释。图 2.18的伪代码体现了这种设计统一性的好处。

The file is such a convenient memory abstraction that in some systems (for example, the UNIX system and its derivatives) every input/output device in a computer system provides a file interface (see Figure 2.19). In such systems, files not only are an abstraction for non-volatile memories (e.g., magnetic disks), but they are also a convenient interface to the keyboard device, the display, communication links, and so on. In such systems, each I/O device has a name in the file naming scheme. A program OPENs the keyboard device, READs bytes from the keyboard device, and then CLOSEs the keyboard device, without having to know any details about the keyboard management procedure, what type of keyboard it is, and the like. Similarly, to interact with the display, a program can OPEN the display device, WRITE to it, and CLOSE it. The program need not know any details about the display. In accordance with the principle of least astonishment, each device management procedure provides some reasonable interpretation for every file system method. The pseudocode of Figure 2.18 exemplifies the benefit of this kind of design uniformity.

图 2.19使用文件抽象和分层来集成不同类型的输入和输出设备。文件系统充当提供统一抽象接口的中介，而各种设备管理器则是将抽象接口转换为不同设备的操作要求的程序。

Figure 2.19 Using the file abstraction and layering to integrate different kinds of input and output devices. The file system acts as an intermediary that provides a uniform, abstract interface, and the various device managers are programs that translate that abstract interface into the operational requirements for different devices.

这种统一接口的一个特点是，在许多情况下，只需重新绑定名称，就可以用文件替换 I/O 设备，反之亦然，而无需以任何方式修改应用程序。这种使用命名来支持模块化的做法在调试应用程序时特别有用。例如，可以通过将一个充满文本的文件放在键盘设备的位置来轻松测试需要键盘输入的程序。由于这些例子，文件系统抽象已被证明非常成功。

One feature of such a uniform interface is that in many situations one can, by simply rebinding the name, replace an I/O device with a file, or vice versa, without modifying the application program in any way. This use of naming in support of modularity is especially helpful when debugging an application program. For example, one can easily test a program that expects keyboard input by slipping a file filled with text in the place of the keyboard device. Because of such examples, the file system abstraction has proven to be very successful.

2.5.1. UNIX文件系统的应用程序编程接口

2.5.1. Application Programming Interface for the UNIX File System

程序可以用用户选择的名称创建文件，读取和写入文件的内容，以及设置和获取文件的元数据。示例元数据包括上次修改时间、文件所有者的用户 ID 以及其他用户的访问权限。（有关元数据的完整讨论，请参见第 3.1.2 节。）为了组织文件，用户可以将它们分组到具有用户选择的名称的目录中，从而创建命名网络。用户还可以将存储在存储设备上的命名网络嫁接到现有的命名网络上，从而允许将不同设备的命名网络合并到单个大型命名网络中。为了支持这些操作，UNIX文件系统提供了表 2.1所示的应用程序编程接口 (API) 。

A program can create a file with a user-chosen name, read and write the file’s content, and set and get a file’s metadata. Example metadata include the time of last modification, the user ID of the file’s owner, and access permissions for other users. (For a full discussion of metadata see Section 3.1.2.) To organize their files, users can group them in directories with user-chosen names, creating a naming network. Users can also graft a naming network stored on a storage device onto an existing naming network, allowing naming networks for different devices to be incorporated into a single large naming network. To support these operations, the UNIX file system provides the application programming interface (API) shown in Table 2.1.

表 2.1. UNIX文件系统应用程序编程接口

Table 2.1. UNIX File System Application Programming Interface

为了解决实现此 API 的问题，UNIX文件系统采用了分而治之的策略。UNIX 文件系统利用多层隐藏的面向机器的名称（即地址）来实现文件。然后，它应用UNIX持久对象命名方案将用户友好的名称映射到这些文件。表 2.2说明了此结构。

To tackle the problem of implementing this API, the UNIX file system employs a divide-and-conquer strategy. The UNIX file system makes use of several hidden layers of machine-oriented names (that is, addresses), one on top of another, to implement files. It then applies the UNIX durable object naming scheme to map user-friendly names to these files. Table 2.2 illustrates this structure.

表 2.2. UNIX文件系统的命名层。

Table 2.2. The naming layers of the UNIX file system.

在本节的其余部分，我们从表 2.2的底层向上到顶层，从系统的最低层向上到用户。此描述与UNIX系统版本 6 的实现非常吻合，后者可以追溯到 20 世纪 70 年代早期。版本 6 有详尽的文档 [进一步阅读建议 2.2.2 ]，并抓住了许多现代UNIX文件系统中的重要思想，但现代版本更为复杂；它们提供了更好的稳健性，并且可以更有效地处理大文件、多文件等。我们将在几个地方指出其中的一些差异，但鼓励读者查阅文件系统文献中的论文，以了解现代UNIX文件系统的工作原理和发展情况。

In the rest of this section we work our way up from the bottom layer of Table 2.2 to the top layer, proceeding from the lowest layer of the system up toward the user. This description corresponds closely to the implementation of Version 6 of the UNIX system, which dates back to the early 1970s. Version 6 is well documented [Suggestions for Further Reading 2.2.2] and captures the important ideas that are found in many modern UNIX file systems, but modern versions are more complex; they provide better robustness and handle large files, many files, and so on, more efficiently. In a few places we will point out some of these differences, but the reader is encouraged to consult papers in the file system literature to find out how modern UNIX file systems work and are evolving.

2.5.2. 块层

2.5.2. The Block Layer

在底层，UNIX文件系统指代一些能够持久存储数据的物理设备，例如磁盘、闪存盘或磁带。此类设备上的存储被分成固定大小的单位，称为块。对于磁盘（参见边栏 2.2），一个块对应于少量的磁盘扇区。块是磁盘空间的最小分配单位，其大小是几个目标之间的权衡。小的块可减少小文件所浪费的磁盘量；如果许多文件小于 4 KB，则 16 KB 的块大小会浪费空间。另一方面，非常小的块大小可能需要较大的数据结构来跟踪空闲块和已分配块。此外，还有一些性能考虑因素也会影响块大小，我们将在第 6 章中讨论其中一些因素。在版本 6 中，UNIX文件系统使用 512 字节的块，但现代UNIX文件系统通常使用 8 KB 的块。

At the bottom layer the UNIX file system names some physical device such as a magnetic disk, flash disk, or magnetic tape that can store data durably. The storage on such a device is divided into fixed-size units, called blocks. For a magnetic disk (see Sidebar 2.2), a block corresponds to a small number of disk sectors. A block is the smallest allocation unit of disk space, and its size is a trade-off between several goals. A small block reduces the amount of disk wasted for small files; if many files are smaller than 4 kilobytes, a 16-kilobyte block size wastes space. On the other hand, a very small block size may incur large data structures to keep track of free and allocated blocks. In addition, there are performance considerations that impact the block size, some of which we discuss in Chapter 6. In version 6, the UNIX file system used 512-byte blocks, but modern UNIX file systems often use 8-kilobyte blocks.

这些块的名称是数字，通常对应于块相对于设备开头的偏移量。在最底层的命名层中，存储设备可以看作是将块号绑定到物理块的上下文。块设备的名称映射算法很简单：它将块号作为输入并返回块。实际上，我们并不真正想要块本身——那将是一堆氧化铁。我们想要的是块的内容，因此该算法实际上实现了块名称和块内容之间的固定映射。如果我们将存储设备表示为块的线性数组，则以下代码片段实现了名称映射算法：

The names of these blocks are numbers, which typically correspond to the offset of the block from the beginning of the device. In the bottom naming layer, a storage device can be viewed as a context that binds block numbers to physical blocks. The name-mapping algorithm for a block device is simple: it takes as input a block number and returns the block. Actually, we don’t really want the block itself—that would be a pile of iron oxide. What we want is the contents of the block, so the algorithm actually implements a fixed mapping between block name and block contents. If we represent the storage device as a linear array of blocks, then the following code fragment implements the name-mapping algorithm:

过程 BLOCK_NUMBER_TO_BLOCK (整数 b )返回 块

procedure BLOCK_NUMBER_TO_BLOCK (integer b) returns block

返回 设备[ b ]

return device[b]

在这个简单的算法中，变量名device指的是某个特定的物理设备。在许多设备中，映射更为复杂。例如，硬盘驱动器可能在末尾保留一组备用块，并将任何损坏的块的块号重新绑定到备用块。硬盘驱动器本身可以分层实现，如第 8.5.4 节 [在线] 中所示。BLOCK_NUMBER_TO_BLOCK 返回的值是块b的内容。

In this simple algorithm the variable name device refers to some particular physical device. In many devices the mapping is more complicated. For example, a hard drive might keep a set of spare blocks at the end and rebind the block numbers of any blocks that go bad to spares. The hard drive may itself be implemented in layers, as will be seen in Section 8.5.4 [on-line]. The value returned by BLOCK_NUMBER_TO_BLOCK is the contents of block b.

名称发现：块的名称是来自紧凑集合的整数，但块层必须跟踪哪些块正在使用以及哪些块可供分配。正如我们将看到的，文件系统通常需要对文件系统在磁盘上的布局进行描述。作为此信息的锚点，UNIX文件系统以超级块开始，该超级块具有众所周知的名称（例如 1）。例如，超级块包含文件系统磁盘的大小（以块为单位）。（块 0 通常存储启动操作系统的小程序；参见边栏 5.3。）

Name discovery: The names of blocks are integers from a compact set, but the block layer must keep track of which blocks are in use and which are available for assignment. As we will see, the file system in general has a need for a description of the layout of the file system on disk. As an anchor for this information, the UNIX file system starts with a super block, which has a well-known name (e.g., 1). The super block contains, for example, the size of the file system’s disk in blocks. (Block 0 typically stores a small program that starts the operating system; see Sidebar 5.3.)

UNIX文件系统的不同实现对空闲块列表使用不同的表示。版本 6 实现将未使用块的块号列表保存在链接列表中，该列表存储在一些未使用块中。此列表的第一个块的块号存储在超级块中。分配块的调用会导致块层中的某个过程在列表数组中搜索空闲块，将其从列表中删除，并返回该块的块号。

Different implementations of the UNIX file system use different representations for the list of free blocks. The version 6 implementation keeps a list of block numbers of unused blocks in a linked list that is stored in some of the unused blocks. The block number of the first block of this list is stored in the super block. A call to allocate a block leads to a procedure in the block layer that searches the list array for a free block, removes it from the list, and returns that block’s block number.

现代UNIX文件系统通常使用位图来跟踪空闲块。位图中的位i记录块i是空闲的还是已分配的。位图本身存储在磁盘上的一个众所周知的位置（例如，紧接着超级块）。图 2.20显示了简单文件系统的可能磁盘布局。它以超级块开始，后面跟着一个位图，用于记录哪些磁盘块正在使用中。位图之后是 inode 表，每个文件都有一个条目（如下所述），后面跟着空闲的或已分配给某个文件的块。超级块包含位图和 inode 表的大小（以块为单位）。

Modern UNIX file systems often use a bitmap for keeping track of free blocks. Bit i in the bitmap records whether block i is free or allocated. The bitmap itself is stored at a well-known location on the disk (e.g., right after the super block). Figure 2.20 shows a possible disk layout for a simple file system. It starts with the super block, followed by a bitmap that records which disk blocks are in use. After the bitmap comes the inode table, which has one entry for each file (as explained next), followed by blocks that are either free or allocated to some file. The super block contains the size of the bitmap and inode table in blocks.

图 2.20简单文件系统的可能磁盘布局。

Figure 2.20 Possible disk layout for a simple file system.

2.5.3. 文件层

2.5.3. The File Layer

用户需要存储大于一个块大小且可能随时间增大或缩小的项目。为了支持此类项目，UNIX文件系统为文件引入了下一层命名层。文件是任意长度的字节的线性数组。文件系统需要以某种方式记录哪些块属于每个文件。为了支持此要求，UNIX文件系统创建了一个索引节点（简称inode），作为文件元数据的容器。我们对 inode 的初始声明是：

Users need to store items that are larger than one block in size and that may grow or shrink over time. To support such items, the UNIX file system introduces a next naming layer for files. A file is a linear array of bytes of arbitrary length. The file system needs to record in some way which blocks belong to each file. To support this requirement, the UNIX file system creates an index node, or inode for short, as a container for metadata about the file. Our initial declaration of an inode is:

结构 inode

structure inode

整数 block_numbers [ N ] // 构成文件的块的编号

integer block_numbers[N]       // the numbers of the blocks that constitute the file

整数 大小        //文件的大小（以字节为单位）

integer size        // the size of the file in bytes

因此，文件的 inode 是一个上下文，其中文件的各个块由整数块号命名。使用此结构，解析文件中块名称的简化名称映射算法如下：

The inode for a file is thus a context in which the various blocks of the file are named by integer block numbers. With this structure, a simplified name-mapping algorithm for resolving the name of a block in a file is as follows:

过程 INDEX_TO_BLOCK_NUMBER ( inode 实例 i ,整数 索引)返回整数

procedure INDEX_TO_BLOCK_NUMBER (inode instance i, integer index) returns integer

返回 i . block_numbers [ index ]

return i.block_numbers[index]

版本 6 UNIX文件系统将此算法用于小文件，小文件限制为N = 8 个块。对于大文件，版本 6 使用更复杂的算法将inode 的第 index个块映射到块号。i.block_numbers 中的前七个条目是间接块。间接块不包含数据，但包含块号。例如，如果块大小为 512 字节，索引为2字节（与版本 6 中一样），则间接块可以包含 256 个 2 字节块号。第八个条目是双间接块（包含间接块的块号的块）。当N = 8 时，这种具有间接和双间接块的设计允许( N − 1) × 256 + 1 × 256 × 256 = 67,329个块，大约 32 兆字节。^*问题集1探讨了一些设计权衡，以允许文件系统支持大文件。一些现代UNIX文件系统使用不同的表示形式或更复杂的数据结构（例如 B+ 树）来实现文件。

The version 6 UNIX file system uses this algorithm for small files, which are limited to N = 8 blocks. For large files, version 6 uses a more sophisticated algorithm for mapping the index-th block of an inode to a block number. The first seven entries in i.block_numbers are indirect blocks. Indirect blocks do not contain data, but block numbers. For example, with a block size of 512 bytes and an index of 2 bytes (as in Version 6), an indirect block can contain 256 2-byte block numbers. The eighth entry is a doubly indirect block (blocks that contain block numbers of indirect blocks). This design with indirect and doubly indirect blocks allows for (N − 1) × 256 + 1 × 256 × 256 = 67,329 blocks when N = 8, about 32 megabytes.^* Problem set 1 explores some design trade-offs to allow the file system to support large files. Some modern UNIX file systems use different representations or more sophisticated data structures, such as B+ trees, to implement files.

UNIX文件系统允许用户通过分层前两种命名方案并将字节数指定为相对于文件开头的偏移量来命名文件中的任何特定字节：

The UNIX file system allows users to name any particular byte in a file by layering the previous two naming schemes and specifying the byte number as an offset from the beginning of the file:

1 过程 INODE_TO_BLOCK (整数 偏移量，inode 实例 i )返回 块

1 procedure INODE_TO_BLOCK (integer offset, inode instance i) returns block

2 o ←偏移量/块大小

2 o ← offset / BLOCKSIZE

3 b ←索引到块号（i，o）

3 b ← INDEX_TO_BLOCK_NUMBER (i, o)

4 返回 BLOCK_NUMBER_TO_BLOCK（b）

4 return BLOCK_NUMBER_TO_BLOCK (b)

返回的值是保存偏移量处字节值的整个块。版本 6 使用3 字节数字表示偏移量，这将最大文件大小限制为 2 ²⁴字节。现代UNIX文件系统使用 64 位数字。该过程返回包含指定字节的整个块。正如我们将在2.5.11 节中看到的那样，READ使用此过程返回请求的字节。

The value returned is the entire block that holds the value of the byte at offset. Version 6 used for offset a 3-byte number, which limits the maximum file size to 2²⁴ bytes. Modern UNIX file systems use a 64-bit number. The procedure returns the entire block that contains the named byte. As we will see in Section 2.5.11, READ uses this procedure to return the requested bytes.

2.5.4. Inode 编号层

2.5.4. The Inode Number Layer

与其传递 inode 本身，不如命名它们并传递它们的名称更方便。为了支持此功能，UNIX文件系统提供了另一个命名层，该层通过 inode 编号命名 inode。实现此命名层的一种方便方法是使用一个直接包含所有 inode 的表，按 inode 编号索引。命名算法如下：

Instead of passing inodes themselves around, it would be more convenient to name them and pass their names around. To support this feature, the UNIX file system provides another naming layer that names inodes by an inode number. A convenient way to implement this naming layer is to employ a table that directly contains all inodes, indexed by inode number. Here is the naming algorithm:

1 过程 INODE_NUMBER_TO_INODE (整数 inode_number )返回 inode

1 procedure INODE_NUMBER_TO_INODE (integer inode_number) returns inode

2 返回 inode_table [ inode_number ]

2 return inode_table[inode_number]

其中inode_table是存储在存储设备上固定位置（例如，在开头）的对象。inode_table的名称映射算法仅返回表的起始块号。

where inode_table is an object that is stored at a fixed location on the storage device (e.g., at the beginning). The name-mapping algorithm for inode_table just returns the starting block number of the table.

名称发现：inode 编号与磁盘块编号一样，是一组紧凑的整数，同样，inode 编号层必须跟踪哪些 inode 编号正在使用以及哪些可以分配。与块编号分配一样，不同的实现使用各种表示法来表示空闲 inode 列表，并提供分配和释放 inode 的调用。在最简单的实现中，inode 包含一个字段来记录它是否空闲。

Name discovery: inode numbers, like disk block numbers, are a compact set of integers, and again the inode number layer must keep track of which inode numbers are in use and which are free to be assigned. As with block number assignment, different implementations use various representations for a list of free inodes and provide calls to allocate and deallocate inodes. In the simplest implementation, the inode contains a field recording whether or not it is free.

通过将这三层放在一起，我们得到以下程序：

By putting these three layers together, we obtain the following procedure:

1 过程 INODE_NUMBER_TO_BLOCK (整数 偏移量，整数 inode_number )

1 procedure INODE_NUMBER_TO_BLOCK (integer offset, integer inode_number)

2 返回 块

2 returns block

3 inode 实例 i ← INODE_NUMBER_TO_INODE ( inode_number )

3 inode instance i ← INODE_NUMBER_TO_INODE (inode_number)

4 o ←偏移量/块大小

4 o ← offset / BLOCKSIZE

5 b ←索引到块号（i，o）

5 b ← INDEX_TO_BLOCK_NUMBER (i, o)

6 返回 BLOCK_NUMBER_TO_BLOCK（b）

6 return BLOCK_NUMBER_TO_BLOCK (b)

此过程返回包含inode_number命名的文件中位于offset处的字节的块。此过程遍历三层命名。存储块有数字、属于 inode 的块的编号索引以及 inode 的数字。

This procedure returns the block that contains the byte at offset in the file named by inode_number. This procedure traverses three layers of naming. There are numbers for storage blocks, numbered indexes for blocks belonging to an inode, and numbers for inodes.

2.5.5. 文件名层

2.5.5. The File Name Layer

数字是计算机使用的便捷名称（数字可以存储在固定长度的字段中，这简化了存储分配），但对于人们使用来说却不方便（数字的助记价值很小）。此外，块和 inode 编号指定一个位置，因此如果需要重新排列物理存储，则数字必须更改，这对人们来说又很不方便。UNIX文件系统通过插入命名层来解决这个问题，该命名层的唯一目的是隐藏文件管理的元数据。在此层之上是用户友好的持久对象命名方案 - 文件和输入/输出设备。此命名方案同样有几层。持久对象命名方案中最明显的组件是目录。在UNIX文件系统中，目录是一个上下文，包含一组字符串名称和 inode 编号之间的绑定。

Numbers are convenient names for use by a computer (numbers can be stored in fixed-length fields that simplify storage allocation) but are inconvenient names for use by people (numbers have little mnemonic value). In addition, block and inode numbers specify a location, so if it becomes necessary to rearrange the physical storage, the numbers must change, which is again inconvenient for people. The UNIX file system deals with this problem by inserting a naming layer whose sole purpose is to hide the metadata of file management. Above this layer is a user-friendly naming scheme for durable objects—files and input/output devices. This naming scheme again has several layers. The most visible component of the durable object naming scheme is the directory. In the UNIX file system, a directory is a context containing a set of bindings between character-string names and inode numbers.

要创建文件，UNIX文件系统会分配一个 inode，初始化其元数据，并将建议的名称绑定到某个目录中的 inode。写入文件时，文件系统会将块分配给 inode。

To create a file, the UNIX file system allocates an inode, initializes its metadata, and binds the proposed name to that inode in some directory. As the file is written, the file system allocates blocks to the inode.

默认情况下，UNIX文件系统会将文件添加到当前工作目录。当前工作目录是对活动应用程序正在工作的目录的上下文引用。上下文引用的形式只是另一个 inode 编号。如果wd是包含正在运行的程序（在UNIX系统中称为进程）的工作目录的状态变量的名称，则可以通过将wd作为第二个参数提供给以下过程来查找刚创建的文件的 inode 编号：

By default, the UNIX file system adds the file to the current working directory. The current working directory is a context reference to the directory in which the active application is working. The form of the context reference is just another inode number. If wd is the name of the state variable that contains the working directory for a running program (called a process in the UNIX system), one can look up the inode number of the just-created file by supplying wd as the second argument to a procedure such as:

过程 NAME_TO_INODE_NUMBER (字符串文件 名，整数 目录)返回整数

procedure NAME_TO_INODE_NUMBER (character string filename, integer dir) returns integer

返回 LOOKUP (文件名,目录)

return LOOKUP (filename, dir)

过程CHDIR（其实现我们将在后面描述）允许进程设置wd。

The procedure CHDIR, whose implementation we describe later, allows a process to set wd.

为了表示目录，UNIX文件系统重用了迄今为止开发的机制：它将目录表示为文件。按照惯例，表示目录的文件包含一个将文件名映射到 inode 编号的表。例如，图 2.21是一个具有两个文件名（“program”和“paper”）的目录，它们分别映射到 inode 编号 10 和 12。在版本 6 中，名称的最大长度为 14 个字节，表中的条目长度固定为 16 个字节（名称为 14 个字节，inode 编号为 2 个字节）。现代UNIX文件系统允许使用可变长度的名称，并且表表示更加复杂。

To represent a directory, the UNIX file system reuses the mechanisms developed so far: it represents directories as files. By convention, a file that represents a directory contains a table that maps file names to inode numbers. For example, Figure 2.21 is a directory with two file names (“program” and “paper”), which are mapped to inode numbers 10 and 12, respectively. In Version 6, the maximum length of a name is 14 bytes, and the entries in the table have a fixed length of 16 bytes (14 for the name and 2 for the inode number). Modern UNIX file systems allow for variable-length names, and the table representation is more sophisticated.

图 2.21目录。

Figure 2.21 A directory.

为了记录 inode 是用于目录还是文件，unix 文件系统使用类型字段扩展了 inode：

To record whether an inode is for a directory or a file, the unix file system extends the inode with a type field:

结构 inode

structure inode

整数 block_numbers [ N ] // 构成文件的块的编号

integer block_numbers[N]       // the numbers of the blocks that constitute the file

整数 大小        //文件的大小（以字节为单位）

integer size        // the size of the file in bytes

整数 类型        //文件类型：常规文件、目录、...

integer type        // type of file: regular file, directory, …

MKDIR创建一个零长度文件（目录）并将类型设置为DIRECTORY。 稍后引入的扩展将为类型添加其他值。

MKDIR creates a zero-length file (directory) and sets type to DIRECTORY. Extensions introduced later will add additional values for type.

通过这种目录和 inode 表示，LOOKUP如下所示：

With this representation of directories and inodes, LOOKUP is as follows:

1 过程 LOOKUP (字符串文件 名，整数 目录)返回整数

1 procedure LOOKUP (character string filename, integer dir) returns integer

2 块 实例 b

2 block instance b

3 inode 实例 i ← INODE_NUMBER_TO_INODE ( dir )

3 inode instance i ← INODE_NUMBER_TO_INODE (dir)

4 如果 i.type ≠ DIRECTORY则返回 FAILURE

4 if i.type ≠ DIRECTORYthen return FAILURE

5 表示 偏移量 从0到i.size - 1

5 for offset from 0 to i.size – 1 do

6 b ← INODE_NUMBER_TO_BLOCK (偏移量，目录)

6 b ← INODE_NUMBER_TO_BLOCK (offset, dir)

7 如果 STRING_MATCH (文件名, b )那么

7 if STRING_MATCH (filename, b) then

8 返回 INODE_NUMBER (文件名，b )

8 return INODE_NUMBER (filename, b)

9 偏移量←偏移量+块大小

9 offset ← offset + BLOCKSIZE

10 返回 失败

10 return FAILURE

LOOKUP读取包含目录dir的数据的块并在目录的数据中搜索字符串filename 。它计算目录第一个块的块号（第6行），然后过程STRING_MATCH（未显示代码）在该块中搜索名称为filename的条目。如果有条目，INODE_NUMBER（未显示代码）返回条目中的 inode 号（第8行）。如果没有条目，LOOKUP计算第二个块的块号，依此类推，直到搜索完目录的所有块。如果所有块都不包含filename的条目，LOOKUP将返回错误（第10行）。例如，调用LOOKUP（“program”，dir），其中dir是图 2.21中目录的 inode 号，将返回 inode 号 10。

LOOKUP reads the blocks that contain the data for the directory dir and searches for the string filename in the directory’s data. It computes the block number for the first block of the directory (line 6) and the procedure STRING_MATCH (no code shown) searches that block for an entry for the name filename. If there is an entry, INODE_NUMBER (no code shown) returns the inode number in the entry (line 8). If there is no entry, LOOKUP computes the block number for the second block, and so on, until all blocks of the directory have been searched. If none of the blocks contain an entry for filename, LOOKUP returns an error (line 10). As an example, an invocation of LOOKUP (“program”, dir), where dir is the inode number for the directory of Figure 2.21, would return the inode number 10.

2.5.6. 路径名称层

2.5.6. The Path Name Layer

将所有文件放在一个目录中会使用户难以跟踪大量文件。枚举大型目录的内容将生成一个很长的列表，该列表的组织方式最多是简单排列（例如按字母顺序排列）。为了允许对用户文件进行任意分组，UNIX文件系统允许用户创建命名目录。

Having all files in a single directory makes it hard for users to keep track of large numbers of files. Enumerating the contents of a large directory would generate a long list that is organized simply (e.g., alphabetically) at best. To allow arbitrary groupings of user files, the UNIX file system permits users to create named directories.

目录可以像文件一样命名，但用户还需要一种命名目录中文件的方法。解决方案是向文件名添加一些结构：例如“projects/paper”，其中“projects”命名目录，“paper”命名该目录中的文件。这些结构化名称就是路径名的示例。UNIX 文件系统使用斜线（正斜杠）作为路径名组件的分隔符；其他系统选择不同的分隔符，例如句点、反斜杠或冒号。使用这些工具，用户可以创建目录和文件的层次结构。

A directory can be named just like a file, but the user also needs a way of naming the files in that directory. The solution is to add some structure to file names: for example, “projects/paper”, in which “projects” names a directory and “paper” names a file in that directory. Structured names such as these are examples of path names. The UNIX file system uses a virgule (forward slash) as a separator of the components of a path name; other systems choose different separator characters such as period, back slash, or colon. With these tools, users can create a hierarchy of directories and files.

路径名的名称解析算法可以通过在先前的目录查找过程中添加递归过程来实现：

The name-resolving algorithm for path names can be implemented by layering a recursive procedure over the previous directory lookup procedure:

1 过程 PATH_TO_INODE_NUMBER (字符串 路径，整数 目录)返回整数

1 procedure PATH_TO_INODE_NUMBER (character string path, integer dir) returns integer

2 如果（PLAIN_NAME（路径））返回 NAME_TO_INODE_NUMBER（路径，目录）

2 if (PLAIN_NAME (path)) return NAME_TO_INODE_NUMBER (path, dir)

3 其他

3 else

4 dir ← LOOKUP ( FIRST (路径), dir )

4 dir ← LOOKUP (FIRST (path), dir)

5 路径← REST (路径)

5 path ← REST (path)

6 返回 PATH_TO_INODE_NUMBER (路径，目录)

6 return PATH_TO_INODE_NUMBER (path, dir)

函数PLAIN_NAME ( path )扫描其参数以查找UNIX标准路径名分隔符（正斜杠），如果未找到则返回TRUE 。如果没有分隔符，程序会将简单名称解析为所请求目录中的 inode 编号（第2行）。如果path中有分隔符，程序会将其视为路径名并开始处理（第4行至第 6行）。函数FIRST从路径中剥离第一个组件名称，REST返回路径名的其余部分。因此，例如，调用PATH_TO_NAME (“projects/paper”, wd ) 会导致递归调用PATH_TO_NAME (“paper”, dir )，其中dir是目录“projects”的 inode 编号。

The function PLAIN_NAME ( path ) scans its argument for the UNIX standard path name separator (forward slash) and returns TRUE if it does not find one. If there is no separator, the program resolves the simple name to an inode number in the requested directory (line 2). If there is a separator in path, the program takes it to be a path name and goes to work on it (lines 4 through 6). The function FIRST peels off the first component name from the path, and REST returns the remainder of the path name. Thus, for example, the call PATH_TO_NAME (“projects/paper”, wd) results in the recursive call PATH_TO_NAME (“paper”, dir), where dir is the inode number for the directory “projects”.

对于路径名，通常需要输入包含许多部分的名称。为了解决这个麻烦，UNIX文件系统支持更改目录过程CHDIR，允许进程设置其工作目录：

With path names, one often has to type names with many components. To address this annoyance, the UNIX file system supports a change directory procedure, CHDIR, allowing a process to set its working directory:

过程 CHDIR (路径 字符串)

procedure CHDIR (path character string)

wd ← PATH_TO_INODE_NUMBER (路径, wd )

wd ← PATH_TO_INODE_NUMBER (path, wd)

当一个进程启动时，它会从创建该进程的父进程继承工作目录。

When a process starts, it inherits the working directory from the parent process that created this process.

2.5.7. 链接

2.5.7. Links

要引用当前工作目录以外的目录中的文件，仍然需要输入长名称。例如，当我们在目录“projects”中工作时（在调用CHDIR（“projects”）之后），我们可能必须经常引用文件“Mail/inbox/new-assignment”。为了解决这个烦恼，UNIX文件系统支持称为链接的同义词。在示例中，我们可能想要在当前工作目录“projects”中为此文件创建一个链接。使用以下参数调用LINK过程：

To refer to files in directories other than the current working directory still requires typing long names. For example, while we are working in the directory “projects”—after calling CHDIR (“projects”)—we might have to refer often to the file “Mail/inbox/new-assignment”. To address this annoyance, the UNIX file system supports synonyms known as links. In the example, we might want to create a link for this file in the current working directory, “projects”. Invoking the LINK procedure with the following arguments:

LINK (“邮件/收件箱/新任务”，“任务”)

LINK (“Mail/inbox/new-assignment”, “assignment”)

如果“assignment”尚不存在，则将“assignment”设为“projects”中“Mail/inbox/new-assignment”的同义词。（如果存在，LINK将返回错误，指出“assignment”已存在。）使用链接，目录层次结构将从严格的层次结构变为有向图。（UNIX文件系统只允许链接到文件，而不允许链接到目录，因此该图不仅是有向的，而且是无环的。我们稍后将看到原因。）

makes “assignment” a synonym for “Mail/inbox/new-assignment” in “projects”, if “assignment” doesn’t exist yet. (If it does, LINK will return an error saying “assignment” already exists.) With links, the directory hierarchy turns from a strict hierarchy into a directed graph. (The UNIX file system allows links only to files, not to directories, so the graph is not only directed but acyclic. We will see why in a moment.)

UNIX文件系统将链接简单地实现为不同上下文中的绑定，将不同的文件名映射到相同的 inode 编号；因此，链接不需要对迄今为止开发的命名方案进行任何扩展。例如，如果“new-assignment”的 inode 编号为 481，则目录“Mail/inbox”包含一个条目 {“new-assignment”, 481}，执行上述命令后，目录“projects”包含一个条目 {“assignment”, 481}。用UNIX系统术语来说，“projects/assignment”现在链接到“Mail/inbox/new-assignment”。

The UNIX file system implements links simply as bindings in different contexts that map different file names to the same inode number; thus, links don’t require any extension to the naming scheme developed so far. For example, if the inode number for “new-assignment” is 481, then the directory “Mail/inbox” contains an entry {“new-assignment”, 481} and after the above command is executed the directory “projects” contains an entry {“assignment”, 481}. In UNIX system jargon, “projects/assignment” is now linked to “Mail/inbox/new-assignment”.

当不再需要某个文件时，进程可以使用UNLINK ( filename ) 删除该文件，向文件系统指示名称filename不再使用。UNLINK会从包含filename的目录中删除filename与其 inode 编号的绑定。 如果此绑定是最后一个包含 inode 编号的绑定，则文件系统还会将filename的 inode 和filename的 inode 块放入空闲列表中。

When a file is no longer needed, a process can remove a file using UNLINK (filename), indicating to the file system that the name filename is no longer in use. UNLINK removes the binding of filename to its inode number from the directory that contains filename. The file system also puts filename’s inode and the blocks of filename’s inode on the free list if this binding is the last one containing the inode’s number.

在我们添加链接之前，文件仅与一个目录中的名称绑定，因此如果进程要求从该目录中删除该名称，文件系统也可以删除该文件。但是现在已添加链接，当进程要求删除名称时，其他目录中可能仍有名称与该文件绑定，在这种情况下不应删除该文件。这引发了一个问题，何时应删除文件？当进程删除文件的最后一个绑定时，UNIX文件系统会删除文件。UNIX 文件系统通过在 inode 中保留引用计数来实现此策略：

Before we added links, a file was bound to a name in only one directory, so if a process asks to delete the name from that directory, the file system can also delete the file. But now that links have been added, when a process asks to delete a name, there may still be names in other directories bound to the file, in which case the file shouldn’t be deleted. This raises the question, when should a file be deleted? The UNIX file system deletes a file when a process removes the last binding for a file. The UNIX file system implements this policy by keeping a reference count in the inode:

结构 inode

structure inode

整数块 号[ N ]

integer block_numbers[N]

整数 大小

integer size

整数 类型

integer type

整数 引用

integer refcnt

每当它与一个 inode 进行绑定时，文件系统就会增加该 inode 的引用计数。为了删除文件，UNIX文件系统提供了一个UNLINK ( filename ) 过程，该过程删除filename指定的绑定。同时，文件系统将相应 inode 中的引用计数减一。如果减少导致引用计数变为零，则表示不再有与该 inode 的绑定，因此文件系统可以释放该 inode 及其对应的块。例如，UNLINK (“Mail/inbox/new-assignment”) 会删除目录“Mail/inbox”中的目录条目“new-assignment”，但不会删除“assignment”，因为取消链接后inode 481 中的refcnt将为 1。只有调用UNLINK (“assignment”) 后，inode 481 及其块才会被释放。

Whenever it makes a binding to an inode, the file system increases the reference count of that inode. To delete a file, the UNIX file system provides an UNLINK(filename) procedure, which deletes the binding specified by filename. At the same time the file system decreases the reference count in the corresponding inode by one. If the decrease causes the reference count to go to zero, that means there are no more bindings to this inode, so the file system can free the inode and its corresponding blocks. For example, UNLINK (“Mail/inbox/new-assignment”) removes the directory entry “new-assignment” in the directory “Mail/inbox”, but not “assignment”, because after the unlink the refcnt in inode 481 will be 1. Only after calling UNLINK (“assignment”) will the inode 481 and its blocks be freed.

仅当命名图中没有循环时，使用引用计数才有效。为确保UNIX命名网络是没有循环的有向图，UNIX文件系统禁止链接到目录。为了解为何要避免循环，考虑目录“a”，其中包含目录“b”。如果程序在包含“a”的目录中调用LINK（“a/b/c”，“a”），则系统将返回错误并且不执行该操作。如果系统执行了此操作，它将创建从“c”到“a”的循环，并将“a”的 inode 中的引用计数增加一。如果程序随后调用UNLINK（“a”），则名称“a”将被删除，但“a”的 inode 和块不会被删除，因为“a”的 inode 中的引用计数仍然为正（因为从“c”到“a”的链接）。但是一旦删除名称“a”，用户将无法再命名目录“a”，也无法删除它。在这种情况下，目录“a”及其子目录将与命名图断开连接，但系统不会将其删除，因为“a”的 inode 中的引用计数仍然为正。可以检测到这种情况，例如通过使用垃圾收集，但这样做的成本很高。相反，设计人员选择了一个更简单的解决方案：不允许链接到目录，这排除了循环的可能性。

Using reference counts works only if there are no cycles in the naming graph. To ensure that the UNIX naming network is a directed graph without cycles, the UNIX file system forbids links to directories. To see why cycles are avoided, consider a directory “a”, which contains a directory “b”. If a program invokes LINK (“a/b/c”, “a”) in the directory that contains “a”, then the system would return an error and not perform the operation. If the system had performed this operation, it would have created a cycle from “c” to “a” and would have increased the reference count in the inode of “a” by one. If a program then invokes UNLINK (“a”), the name “a” is removed, but the inode and the blocks of “a” wouldn’t be removed because the reference count in the inode of “a” is still positive (because of the link from “c” to “a”). But once the name “a” would be removed, a user would no longer be able to name the directory “a” and wouldn’t be able to remove it either. In that case, the directory “a” and its subdirectories would be disconnected from the naming graph, but the system would not remove it because the reference count in the inode of “a” is still positive. It is possible to detect this situation, for example by using garbage collection, but it is expensive to do so. Instead, the designers chose a simpler solution: don’t allow links to directories, which rules out the possibility of cycles.

但是，有两种特殊情况。首先，默认情况下，每个目录都包含指向其自身的链接；UNIX文件系统为此保留了字符串“.”（一个点）。因此，名称“.”允许进程命名当前目录，而无需知道它是哪个目录。创建目录时，目录的 inode 具有两个引用计数：一个用于目录的 inode，一个用于链接“.”，因为它指向自身。由于“.”引入了长度为 0 的循环，因此在删除目录时不存在命名网络部分断开的风险。取消链接目录时，文件系统只会将目录的 inode 的引用计数减少 2。

There are two special cases, however. First, by default each directory contains a link to itself; the UNIX file system reserves the string “.” (a single dot) for this purpose. The name “.” thus allows a process to name the current directory without knowing which the directory it is. When a directory is created, the directory’s inode has a reference count of two: one for the inode of the directory and one for the link “.”, because it points to itself. Because “.” introduces a cycle of length 0, there is no risk that part of the naming network will become disconnected when removing a directory. When unlinking a directory, the file system just decreases the reference count of the directory’s inode by 2.

其次，默认情况下，每个目录还包含指向父目录的链接；文件系统为此保留了字符串“..”（两个连续的点）。名称“..”允许进程命名父目录，例如，通过调用CHDIR（“..”）向上移动文件层次结构。链接不会造成问题。只有当目录除了“.”和“..”之外没有其他条目时，才能将其删除。如果用户想要删除包含目录“b”的目录“a”，则文件系统会拒绝执行此操作，直到用户先删除“b”。此规则确保命名网络不会断开连接。

Second, by default, each directory also contains a link to a parent directory; the file system reserves the string “..” (two consecutive dots) for this purpose. The name “..” allows a process to name a parent directory and, for example, move up the file hierarchy by invoking CHDIR (“..”). The link doesn’t create problems. Only when a directory has no other entries than “.” and “..” can it be removed. If a user wants to remove a directory “a”, which contains a directory “b”, then the file system refuses to do so until the user first has removed “b”. This rule ensures that the naming network cannot become disconnected.

2.5.8. 重命名

2.5.8. Renaming

使用LINK和UNLINK，版本 6 实现RENAME ( from_name , to_name ) 如下：

Using LINK and UNLINK, Version 6 implemented RENAME (from_name, to_name) as follows:

1 取消链接（到名称）

1 UNLINK (to_name)

2 链接（来自名称，到名称）

2 LINK (from_name, to_name)

3 取消链接（来自名称）

3 UNLINK (from_name)

然而，这种实现有一个不良特性。程序经常使用RENAME将文件的工作副本更改为正式版本；例如，用户可能正在编辑文件“x”。文本编辑器实际上将所有更改都放到临时文件“#x”中。当用户保存文件时，编辑器会将临时文件“#x”重命名为“x”。

This implementation, however, has an undesirable property. Programs often use RENAME to change a working copy of a file into the official version; for example, a user may be editing a file “x”. The text editor actually makes all changes to a temporary file “#x”. When the user saves the file, the editor renames the temporary file “#x” to “x”.

使用LINK和UNLINK实现RENAME 的问题在于，如果计算机在步骤 1 和步骤 2 之间出现故障，然后重新启动，则名称to_name（在本例中为“x”）将丢失，这可能会让用户感到惊讶，因为他们不太可能知道该文件仍然存在，只是名称为“#x”。真正需要的是，通过单个原子操作将“#x”重命名为“x”，但这需要原子操作，这是第 9 章 [在线] 的主题。

The problem with implementing RENAME using LINK and UNLINK is that if the computer fails between steps 1 and 2 and then restarts, the name to_name (“x” in this case) will be lost, which is likely to surprise the user, who is unlikely to know that the file still exists but under the name “#x”. What is really needed is that “#x” be renamed to “x” in a single, atomic operation, but that requires atomic actions, which are the topic of Chapter 9 [on-line].

如果没有原子操作，则可以为RENAME实现以下稍弱的规范：如果to_name已经存在，则to_name的实例将始终存在，即使系统在RENAME中间失败。此规范足以让编辑器做正确的事情，并且是现代版本提供的。

Without atomic actions, it is possible to implement the following slightly weaker specification for RENAME: if to_name already exists, an instance of to_name will always exist, even if the system should fail in the middle of RENAME. This specification is good enough for the editor to do the right thing and is what modern versions provide.

现代版本实质上实现此规范如下：

Modern versions implement this specification in essence as follows:

1 链接（发件人名称，收件人名称）

1 LINK (from_name, to_name)

2 取消链接（来自名称）

2 UNLINK (from_name)

因为无法链接到已存在的名称，所以RENAME通过直接操作文件系统结构来实现这两个调用的效果。RENAME首先将to_name目录条目中的 inode 编号更改为磁盘上from_name的 inode 编号。 然后， RENAME删除from_name的目录条目。 如果文件系统在这两个步骤之间发生故障，则在恢复时，文件系统必须增加from_name的 inode中的引用计数，因为from_name和to_name都指向该 inode。 此实现确保如果to_name在调用RENAME之前存在，它将继续存在，即使计算机在RENAME期间发生故障。

Because one cannot link to a name that already exists, RENAME implements the effects of these two calls by manipulating the file system structures directly. RENAME first changes the inode number in the directory entry for to_name to the inode number for from_name on disk. Then, RENAME removes the directory entry for from_name. If the file system fails between these two steps, then on recovery the file system must increase the reference count in from_name’s inode because both from_name and to_name are pointing to the inode. This implementation ensures that if to_name exists before the call to RENAME, it will continue to exist, even if the computer fails during RENAME.

2.5.9. 绝对路径名层

2.5.9. The Absolute Path Name Layer

UNIX系统为每个用户提供了一个个人目录，称为用户主目录。当用户登录到UNIX系统时，它会启动一个命令解释器（称为shell），用户可以通过它与系统交互。shell 以工作目录( wd )启动，该目录设置为用户主目录的 inode 编号。通过上述过程，用户可以创建个人目录树来组织其主目录中的文件。

The UNIX system provides each user with a personal directory, called a user’s home directory. When a user logs on to a UNIX system, it starts a command interpreter (known as the shell) through which a user can interact with the system. The shell starts with the working directory (wd) set to the inode number of the user’s home directory. With the above procedures, users can create personal directory trees to organize the files in their home directory.

但是，拥有多个个人目录树并不允许用户与另一个用户共享文件。为此，一个用户需要一种引用属于另一个用户的文件名称的方法。实现此目的的最简单方法是将每个用户的名称绑定到该用户的顶级目录，在每个用户都可以使用的某些上下文中。但是，需要命名这个系统范围的上下文。通常，还需要其他系统范围的上下文，例如包含共享程序库的目录。为了用最少的附加机制满足这些需求，文件系统提供了一个通用上下文，称为根目录。根目录包含用户目录、包含程序库的目录以及任何其他广泛共享的目录的绑定。结果是系统的所有文件都集成到基于根的单个目录树（具有受限制的交叉链接）中。

But having several personal directory trees does not allow one user to share files with another. To do that, one user needs a way of referring to the names of files that belong to another user. The easiest way to accomplish that is to bind a name for each user to that user’s top-level directory, in some context that is available to every user. But then there is a requirement to name this systemwide context. Typically, there are needs for other systemwide contexts, such as a directory containing shared program libraries. To address these needs with a minimum of additional mechanisms, the file system provides a universal context, known as the root directory. The root directory contains bindings for the directory of users, the directory containing program libraries, and any other widely shared directories. The result is that all files of the system are integrated into a single directory tree (with restricted cross-links) based on the root.

这种设计留下了一个名称发现问题：用户如何命名根目录？回想一下，名称查找需要上下文引用（目录 inode 的名称），到目前为止，目录 inode 一直由工作目录状态变量提供。要实现根目录，文件系统只需将 inode 编号 1 声明为根目录的 inode。然后，任何用户都可以使用这个众所周知的名称作为起始上下文，在其中查找共享上下文或其他用户的名称（甚至可以查找自己的名称，以便在登录时设置工作目录）。

This design leaves a name discovery question: how can a user name the root directory? Recall that name lookup requires a context reference—the name of a directory inode—and until now that directory inode has been supplied by the working directory state variable. To implement the root, the file system simply declares inode number 1 to be the inode for the root directory. This well-known name can then be used by any user as the starting context in which to look up the name of a shared context, or another user (or even to look up one’s own name, to set the working directory when logging in).

文件系统实际上提供了两种方法来引用根目录中的内容。从系统中的任何目录开始，可以使用名称“..”来命名该目录的父目录，“../..”来命名该目录上方的目录，依此类推，直到到达根目录。用户可以知道已到达根目录，因为根目录中的“..”命名了根目录。也就是说，在根目录中，“.”和“..”都是指向根目录的链接。另一种方法是使用绝对路径名，在UNIX文件系统中，绝对路径名是以“/”开头的名称，例如“/Alice/Mail/inbox/new-assignment”。

The file system actually provides two ways to refer to things in the root directory. Starting from any directory in the system, one can use the name “..” to name that directory’s parent, “../..” to name the directory above that, and so on until the root directory is reached. A user can tell that the root directory is reached, because “..” in the root directory names the root directory. That is, in the root directory, both “.” and “..” are links to the root directory. The other way is with absolute path names, which in the UNIX file system are names that start with a “/”, for example, “/Alice/Mail/inbox/new-assignment”.

为了支持绝对路径名和相对路径名，我们需要在命名方案中增加一层：

To support absolute path names as well as relative path names, we need one more layer in the naming scheme:

1 过程 GENERALPATH_TO_INODE_NUMBER (字符串 路径)返回整数

1 procedure GENERALPATH_TO_INODE_NUMBER (character string path) returns integer

2 如果（路径[0] = “/”）返回 PATH_TO_INODE_NUMBER（路径，1）

2 if (path[0] = “/”) return PATH_TO_INODE_NUMBER(path, 1)

3 否则返回 PATH_TO_INODE_NUMBER ( path，wd )

3 else return PATH_TO_INODE_NUMBER(path, wd)

此时，我们已完成命名方案，该方案可用于命名和共享单个磁盘上的持久存储。例如，要找到与图 2.22中的信息对应的文件“/programs/pong.c”对应的块，我们首先找到 inode 表，该表从存储在超级块（本图中未显示，但请参见图2.20）中的块号（在我们的示例中为块 4）开始。从那里我们找到根 inode（已知为 inode 编号 1）。根 inode 包含块号，而块号又包含根目录的块；在图中，根从块号 14 开始。块 14 列出了根目录中的条目：“programs”由 inode 编号 7 命名。inode 表显示 inode 编号 7 的数据从块号 23 开始，其中包含“ programs ”目录的内容。文件“pong.c”以 inode 编号 9 命名。再次参考 inode 表，查看 inode 9 的存储位置，我们看到与 inode 9 相对应的数据从块编号 61 开始。简而言之，目录和文件经过精心布局，以便可以从根 inode 的已知位置开始找到所有信息。

At this point we have completed a naming scheme that allows us to name and share durable storage on a single disk. For example, to find the blocks corresponding to the file “/programs/pong.c” with the information in Figure 2.22, we start by finding the inode table, which starts at a block number (block 4 in our example) stored in the super block (not shown in this figure, but see Figure 2.20). From there we locate the root inode (which is known to be inode number 1). The root inode contains the block numbers that in turn contain the blocks of the root directory; in the figure the root starts in block number 14. Block 14 lists the entries in the root directory: “programs” is named by inode number 7. The inode table says that data for inode number 7 starts in block number 23, which contains the contents of the “programs” directory. The file “pong.c” is named by inode number 9. Referring once more to the inode table, to see where inode 9 is stored, we see that the data corresponding to inode 9 starts in block number 61. In short, directories and files are carefully laid out so that all information can be found by starting from the well-known location of the root inode.

图 2.22 UNIX文件系统的磁盘布局示例，通过关注 inode 表和数据块来细化图 2.20。inode表是一组连续的块，起始于超级块（未显示）中众所周知的地址。在此示例中，块 4、5 和 6 包含 inode 表，而块 7-61 包含目录和文件。根 inode 按照惯例是众所周知的 inode #1。通常，inode 小于块，因此在此示例中，每个块中有四个 inode。块 #14、#37 和 #16 构成根目录，而块 #23 是名为“/programs”的目录的四个块中的第一个，块 #61 是三块文件“/programs/pong.c”的第一个块。

Figure 2.22 Example disk layout for a UNIX file system, refining Figure 2.20 by focusing on the inode table and data blocks. The inode table is a group of contiguous blocks starting at a well-known address, found in the super block (not shown). In this example, blocks 4, 5, and 6 contain the inode table, while blocks 7–61 contain directories and files. The root inode is by convention the well-known inode #1. Typically, inodes are smaller than a block, so in this example there are four inodes in each block. Blocks #14, #37, and #16 constitute the root directory, while block #23 is the first of four blocks of the directory named “/programs”, and block #61 is the first block of the three-block file “/programs/pong.c”.

版本 6 中的默认根目录是 inode 1。版本 7 添加了一个调用CHROOT来更改进程的根目录。例如，可以通过将 Web 服务器的根目录更改为“/tmp”等，在UNIX名称空间的一角运行 Web 服务器。调用此调用后，Web 服务器的根目录对应于目录“/tmp”的 inode 编号，“/tmp”中的“..”是指向“/tmp”的链接。因此，服务器只能命名“/tmp”下的目录和文件。

The default root directory in Version 6 is inode 1. Version 7 added a call, CHROOT, to change the root directory for a process. For example, a Web server can be run in the corner of the UNIX name space by changing its root directory to, for example, “/tmp”. After this call, the root directory for the Web server corresponds to the inode number of the directory “/tmp” and “..” in “/tmp” is a link to “/tmp”. Thus, the server can name only directories and files below “/tmp”.

2.5.10. 符号链接层

2.5.10. The Symbolic Link Layer

为了允许用户命名其他磁盘上的文件，UNIX文件系统支持将新磁盘附加到命名空间的操作。用户可以选择每个设备所附加的名称：例如，过程

To allow users to name files on other disks, the UNIX file system supports an operation to attach new disks to the name space. A user can choose the name under which each device is attached: for example, the procedure

挂载（“/dev/fd1”，“/flash”）

MOUNT (“/dev/fd1”, “/flash”)

将存储在名为“/dev/fd1”的物理设备上的目录树移植到目录“/flash”上。（此命令表明每个设备在我们描述的相同对象名称空间中也有一个名称；与设备相对应的文件通常包含有关设备本身的信息。）通常，挂载不会在关机后继续存在：重新启动后，用户必须明确重新挂载设备。将优雅的UNIX方法与 DOS 方法进行对比是很有趣的，在 DOS 方法中，设备由固定的单字符名称命名（例如“C:”​​）。

grafts the directory tree stored on the physical device named “/dev/fd1” onto the directory “/flash”. (This command demonstrates that each device also has a name in the same object name space we have been describing; the file corresponding to a device typically contains information about the device itself.) Typically mounts do not survive a shutdown: after a reboot, the user has to explicitly remount the devices. It is interesting to contrast the elegant UNIX approach with the DOS approach, in which devices are named by fixed one-character names (e.g., “C:”).

UNIX文件系统通过在内存中记录“flash”的 inode 来实现MOUNT ，即文件系统已安装在该 inode 上，并将该 inode 保留在内存中，直到至少执行相应的UNMOUNT 。在内存中，系统还会记录已安装在该 inode 上的文件系统的设备和根 inode 编号。此外，它还会在内存中记录“/dev/fd1”的 inode 版本，即其父 inode 是什么。

The UNIX file system implements MOUNT by recording in the in-memory inode for “flash” that a file system has been mounted on it and keeps this inode in memory until at least the corresponding UNMOUNT. In memory, the system also records the device and the root inode number of the file system that has been mounted on it. In addition, it records in the in-memory version of the inode for “/dev/fd1” what its parent inode is.

挂载点的信息全部记录在易失性存储器中，而不是磁盘上，并且不会在计算机故障后继续存在。发生故障后，系统管理员或程序必须再次调用MOUNT。支持MOUNT还需要更改文件名层：如果LOOKUP遇到挂载了文件系统的 inode，它会使用挂载文件系统的根 inode 进行查找。

The information for mount points is all recorded in volatile memory instead of on disk and doesn’t survive a computer failure. After a failure, the system administrator or a program must invoke MOUNT again. Supporting MOUNT also requires a change to the file name layer: if LOOKUP runs into an inode on which a file system is mounted, it uses the root inode of the mounted file system for the lookup.

UNMOUNT撤消挂载。

UNMOUNT undoes the mount.

对于已挂载的文件系统，同义词成为一个更困难的问题，因为每个已挂载的文件系统都有一个 inode 编号的地址空间。每个 inode 编号都有一个默认上下文：它所在的磁盘。因此，一个磁盘上的目录条目无法绑定到不同磁盘上的 inode 编号。这个问题可以通过多种方式解决，其中两种是：(1) 使 inode 在所有磁盘上唯一或 (2) 以不同的方式为其他磁盘上的文件创建同义词。UNIX系统选择第二种方法，即使用称为符号或软链接的间接名称，将一个文件名绑定到另一个文件名。大多数系统都使用方法 (2)，因为尝试保持 inode 编号在全球范围内唯一、较小并且解析速度快会比较复杂。

With mounted file systems, synonyms become a more difficult problem because per mounted file system there is an address space of inode numbers. Every inode number has a default context: the disk on which it is located. Thus, there is no way for a directory entry on one disk to bind to an inode number on a different disk. This problem can be approached in several ways, two of which are: (1) make inodes unique across all disks or (2) create synonyms for files on other disks in a different way. The UNIX system chooses the second approach by using indirect names called symbolic or soft links, which bind a file name to another file name. Most systems use method (2) because of the complications that would be involved in trying to keep inode numbers universally unique, small in size, and fast to resolve.

使用过程SYMLINK，用户可以为同一文件系统中的文件或已挂载文件系统中的文件创建同义词。文件系统通过允许 inode 的类型字段为 SYMLINK 来实现过程SYMLINK ，该过程指示与 inode 关联的块是包含数据还是路径名：

Using the procedure SYMLINK, users can create synonyms for files in the same file system or for files in mounted file systems. The file system implements the procedure SYMLINK by allowing the type field of an inode to be a SYMLINK, which tells whether the blocks associated with the inode contain data or a path name:

结构 inode

structure inode

整数块 号[ N ]

integer block_numbers[N]

整数 大小

integer size

整数 类型        //inode 的类型：常规文件、目录、符号链接、...

integer type        // Type of inode: regular file, directory, symbolic link, …

整数 引用

integer refcnt

如果type字段的值为SYMLINK ，那么数组blocks [ i ]中的数据实际上包含路径名的字符，而不是一组 inode 编号。

If the type field has value SYMLINK, then the data in the array blocks[i] actually contains the characters of a path name rather than a set of inode numbers.

软链接可以通过在GENERALPATH_TO_NODE_NUMBER上分层来实现：

Soft links can be implemented by layering them over GENERALPATH_TO_NODE_NUMBER:

1 过程 PATHNAME_TO_INODE (字符串文件 名)返回 inode

1 procedure PATHNAME_TO_INODE (character string filename) returns inode

2 inode 实例 i

2 inode instance i

3 inode_number ← GENERALPATH_TO_INODE_NUMBER (文件名)

3 inode_number ← GENERALPATH_TO_INODE_NUMBER (filename)

4 我← INODE_NUMBER_TO_INODE ( inode_number )

4 i ← INODE_NUMBER_TO_INODE (inode_number)

5 如果 i.type = SYMBOLIC那么

5 if i.type = SYMBOLICthen

6 i = GENERALPATH_TO_INODE_NUMBER（COERCE_TO_STRING（i.block_numbers））

6 i = GENERALPATH_TO_INODE_NUMBER (COERCE_TO_STRING (i.block_numbers))

7 返回 我

7 return i

PATHNAME_TO_INODE返回的值是filename所命名文件的 inode 的内容。该过程首先查找filename的 inode 编号。然后，它使用INODE_NUMBER_TO_INODE查找 inode 。如果 inode 指示此文件是符号链接，则该过程将文件数据的内容解释为路径名，并再次调用GENERALPATH_TO_INODE_NUMBER 。

The value returned by PATHNAME_TO_INODE is the contents of the inode for the file named by filename. The procedure first looks up the inode number for filename. Then, it looks up the the inode using INODE_NUMBER_TO_INODE. If the inode indicates that this file is a symbolic link, the procedure interprets the contents of data of the file as a path name and invokes GENERALPATH_TO_INODE_NUMBER again.

我们现在有两种类型的同义词。直接绑定到 inode 编号的称为硬链接，以将其与软链接区分开来。继续前面的示例，指向“Mail/inbox/new-assignment”的软链接将包含字符串“Mail/inbox/new-assignment”，而不是 inode 编号 481。软链接是间接名称的一个例子：它将名称绑定到同一名称空间中的另一个名称，而硬链接将名称绑定到 inode 编号，后者是下层名称空间中的名称。因此，软链接依赖于文件名“Mail/inbox/new-assignment”，如果用户更改文件的名称或删除文件，那么链接“projects/assignment”将最终成为悬空引用（第 3.1.6 节讨论悬空引用）。但由于它按名称而不是按 inode 编号链接，因此软链接可以指向不同磁盘上的文件。

We now have two types of synonyms. A direct binding to an inode number is called a hard link, to distinguish it from a soft link. Continuing an earlier example, a soft link to “Mail/inbox/new-assignment” would contain the string “Mail/inbox/new-assignment”, rather than the inode number 481. A soft link is an example of an indirect name: it binds a name to another name in the same name space, while a hard link binds a name to an inode number, which is a name in a lower-layer name space. As a result, the soft link depends on the file name “Mail/inbox/new-assignment” if the user changes the file’s name or deletes the file, then “projects/assignment”, the link, will end up as a dangling reference (Section 3.1.6 discusses dangling references). But because it links by name rather than by inode number, a soft link can point to a file on a different disk.

回想一下，UNIX系统禁止硬链接循环，以便它可以使用引用计数来检测何时可以安全地回收文件的磁盘空间。但是，您仍然可以使用软链接形成循环：例如，树中深层的名称可以命名树中高处的目录。生成的结构不再是有向无环图，而是完全通用的命名网络。使用软链接，程序甚至可以调用SYMLINK（“cycle”，“cycle”），为没有关联文件的文件名创建同义词！如果进程打开这样的文件，它将仅沿着链接链执行一定数量的步骤，然后报告错误，例如“软链接层级过多”。

Recall that the UNIX system forbids cycles of hard links, so that it can use reference counts to detect when it is safe to reclaim the disk space for a file. However, you can still form cycles with soft links: a name deep down in the tree can, for example, name a directory high up in the tree. The resulting structure is no longer a directed acyclic graph, but a fully general naming network. Using soft links, a program can even invoke SYMLINK (“cycle”, “cycle”), creating a synonym for a file name that doesn’t have a file associated with it! If a process opens such a file, it will follow the link chain only a certain number of steps before reporting an error such as “Too many levels of soft links”.

软链接还有另一个有趣的行为。假设工作目录是“/Scholarly/programs/www”，并且该工作目录包含一个名为“CSE499-web”的符号链接，指向“/Scholarly/CSE499/www”。以下调用

Soft links have another interesting behavior. Suppose that the working directory is “/Scholarly/programs/www” and that this working directory contains a symbolic link named “CSE499-web” to “/Scholarly/CSE499/www”. The following calls

CHDIR（“CSE499-web”）

CHDIR (“CSE499-web”)

CHDIR（“..”）

CHDIR (“..”)

让调用者留在“/Scholarly/CSE499”而不是回到用户开始的位置。原因是“..”在新的默认上下文“/Scholarly/CSE499/www”中解析，而不是在可能是预期的上下文“/Scholarly/programs/www”中解析。这种行为可能是可取的，也可能不是，但它是 UNIX 命名语义的直接结果；Plan 9 系统有一个不同的计划，^*这也将在练习 3.2 和 3.3 中进行探讨。

leave the caller in “/Scholarly/CSE499” rather than back where the user started. The reason is that “..” is resolved in the new default context, “/Scholarly/CSE499/www”, rather than what might have been the intended context, “/Scholarly/programs/www”. This behavior may be desirable or not, but it is a direct consequence of the UNIX naming semantics; the Plan 9 system has a different plan,^* which is also explored in exercises 3.2 and 3.3.

总之，UNIX对象命名方案的大部分功能都来自于其命名层。表 ​​2.3重复了表 2.2，这次显示了每个层接口使用的名称、值、上下文和伪代码过程。（尽管我们已经检查了此表中的每一层，但我们演示的算法在某些情况下以表中未建议的方式跨层桥接。）一般的设计技术是为每个问题引入另一层命名，这是通过间接方式解耦模块的原理的应用。

In summary, much of the power of the UNIX object naming scheme comes from its layers of naming. Table 2.3 reprises Table 2.2, this time showing the name, value, context, and pseudocode procedure used at each layer interface. (Although we have examined each of the layers in this table, the algorithms we have demonstrated have in some cases bridged across layers in ways not suggested by the table.) The general design technique has been to introduce for each problem another layer of naming, an application of the principle decouple modules with indirection.

表 2.3 unix 命名层，以及每层的命名方案的详细信息。

Table 2.3 The unix naming layers, with details of the naming scheme of each layer.

2.5.11. 实现文件系统 API

2.5.11. Implementing the File System API

在描述UNIX文件系统的结构时，我们看到了它如何实现CHDIR、MKDIR、LINK、UNLINK、RENAME、SYMLINK、MOUNT和UNMOUNT 。我们通过描述OPEN、READ、WRITE和CLOSE的实现来完成对文件系统 API 的描述。在描述它们的实现之前，我们先描述它们必须支持哪些功能。

In the process of describing how the UNIX file system is structured, we saw how it implements CHDIR, MKDIR, LINK, UNLINK, RENAME, SYMLINK, MOUNT, and UNMOUNT. We complete the description of the file system API by describing the implementation of OPEN, READ, WRITE, and CLOSE. Before describing their implementation, we describe what features they must support.

文件系统允许用户控制谁有权访问他们的文件。文件所有者可以指定其他用户以何种权限访问该文件。例如，所有者可以指定其他用户只有读取文件的权限，而没有写入文件的权限。OPEN必须检查调用者是否具有适当的权限。作为一种复杂操作，一个文件可以由一组用户拥有。第 11 章 [在线] 详细讨论了安全性，因此我们在此略过细节。

The file system allows users to control who has access to their files. An owner of a file can specify with what permissions other users can make accesses to the file. For example, the owner may specify that other users have permission only to read a file but not to write it. OPEN must check whether the caller has the appropriate permissions. As a sophistication, a file can be owned by a group of users. Chapter 11 [on-line] discusses security in detail, so we will skip the details here.

文件系统会记录时间戳，以记录上次访问、上次修改文件以及上次更改文件 inode 的日期和时间。此信息对于增量备份等程序非常重要，因为这些程序必须确定自上次备份运行以来哪些文件已发生更改。文件系统过程必须更新这些值。例如，READ更新上次访问时间，WRITE更新上次修改时间和更改时间，LINK更新上次更改时间。

The file system records timestamps that capture the date and time of the last access, last modification to a file, and last change to a file’s inode. This information is important for programs such as incremental backup, which must determine which files have changed since the last time backup ran. The file system procedures must update these values. For example, READ updates last access time, WRITE updates last modification time and change time, and LINK updates last change time.

OPEN返回文件的简称，称为文件描述符( fd )，READ、WRITE和CLOSE使用它来命名文件。每个进程都以三个打开的​​文件开始：“标准输入”（文件描述符 0）、“标准输出”（文件描述符 1）和“标准错误”（文件描述符 2）。文件描述符可以命名键盘设备、显示设备或磁盘上的文件；程序不需要知道。这种设置允许设计人员在开发程序时不必担心程序的输入来自何处以及程序的输出要到哪里；程序只需从文件描述符 0 读取并写入文件描述符 1。

OPEN returns a short name for a file, called a file descriptor (fd), which READ, WRITE, and CLOSE use to name the file. Each process starts with three open files: “standard in” (file descriptor 0), “standard out” (file descriptor 1), and “standard error” (file descriptor 2). A file descriptor may name a keyboard device, a display device, or a file on disk; a program doesn’t need to know. This setup allows a designer to develop a program without having to worry about where the program’s input is coming from and where the program’s output is going to; the program just reads from file descriptor 0 and writes to file descriptor 1.

多个进程可以并发使用一个文件（例如，多个进程可能会写入显示设备）。如果多个进程打开同一个文件，则它们的READ和WRITE操作对该文件有自己的文件游标。如果一个进程打开一个文件，然后将该文件的文件描述符传递给另一个进程，则这两个进程共享该文件的游标。后一种情况很常见，因为在UNIX系统中，当一个进程（父进程）启动另一个进程（子进程）时，子进程会从父进程继承所有打开的文件描述符。例如，这种设计允许父进程和子进程正确地共享一个公共的输出文件。例如，如果子进程在父进程写入输出文件之后写入该文件，则子进程的输出将出现在父进程的输出之后，因为它们共享游标。

Several processes can use a file concurrently (e.g., several processes might write to the display device). If several processes open the same file, their READ and WRITE operations have their own file cursor for that file. If one process opens a file, and then passes the file descriptor for that file to another process, then the two processes share the cursor of the file. This latter case is common because in the UNIX system when one process (the parent) starts another process (the child), the child inherits all open file descriptors from the parent. This design allows the parent and child, for instance, to share a common output file correctly. If the child writes to the output file, for example, after the parent has written to it, the output of the child appears after the output of the parent because they share the cursor.

如果一个进程打开了一个文件，而另一个进程删除了指向该文件的最后一个名称，则直到第一个进程调用CLOSE时，才会释放 inode 。

If one process has a file open and another process removes the last name pointing to that file, the inode isn’t freed until the first process calls CLOSE.

为了支持这些功能，inode 进行了如下扩展：

To support these features, the inode is extended as follows:

结构 inode

structure inode

整数 block_numbers [ N ] // 构成文件的块数

integer block_numbers[N]       // the number of blocks that constitute the file

整数 大小       //文件的大小（以字节为单位）

integer size       // the size of the file in bytes

整数 类型       //文件类型：常规文件，目录，符号链接

integer type       // type of file: regular file, directory, symbolic link

整数 refcnt        // 此 inode 的名称数量

integer refcnt       // count of the number of names for this inode

integer userid        // 拥有此 inode 的用户 ID

integer userid       // the user ID that owns this inode

整数 groupid        // 拥有此 inode 的组 ID

integer groupid       // the group ID that owns this inode

整数 模式       // inode 的权限

integer mode       // inode’s permissions

整数 atime        // 上次访问的时间（读、写，...）

integer atime       // time of last access (READ, WRITE, … )

整数 mtime        //最后修改的时间

integer mtime       // time of last modification

整数 ctime        // inode 最后一次改变的时间

integer ctime       // time of last change of inode

为了实现OPEN、READ、WRITE和CLOSE，文件系统在内存中保留了几个表：一个文件表（file_table）和每个进程的文件描述符表（fd_table）。文件表记录了进程已打开的文件的信息（即，OPEN成功，但尚未调用CLOSE 的文件）。对于每个打开的文件，此信息包括文件的 inode 编号、文件游标以及记录打开该文件的进程数的引用计数。文件描述符表记录每个文件描述符在文件表中的索引。由于文件的游标存储在 file_table而不是fd_table中，因此子进程可以与其父进程共享继承文件的游标。

To implement OPEN, READ, WRITE, and CLOSE, the file system keeps in memory several tables: one file table (file_table) and for each process a file descriptor table (fd_table). The file table records information for the files that processes have open (i.e., files for which OPEN was successful, but for which CLOSE hasn’t been called yet). For each open file, this information includes the inode number of the file, its file cursor, and a reference count recording how many processes have the file open. The file descriptor table records for each file descriptor the index into the file table. Because a file’s cursor is stored in the file_table instead of the fd_table, children can share the cursor for an inherited file with their parent.

利用这些信息，OPEN实现如下：

With this information, OPEN is implemented as follows:

1 程序 OPEN（字符串文件 名，标志，模式）

1 procedure OPEN (character string filename, flags, mode)

2 inode_number ← PATH_TO_INODE_NUMBER (文件名, wd )

2 inode_number ← PATH_TO_INODE_NUMBER (filename, wd)

3 if inode_number = FAILURE and flags = O_CREATE then        // 创建文件？

3 if inode_number = FAILUREand flags = O_CREATEthen       // Create the file?

4 inode_number ← CREATE ( filename, mode ) // 是的，创建它。

4 inode_number ← CREATE (filename, mode)       // Yes, create it.

5 如果 inode_number = FAILURE那么

5 if inode_number = FAILUREthen

6 返回 失败

6 return FAILURE

7 inode ← INODE_NUMBER_TO_INODE ( inode_number )

7 inode ← INODE_NUMBER_TO_INODE (inode_number)

8 if PERMITTED ( inode , flags ) then        //此用户是否具有所需的权限

8 if PERMITTED (inode, flags) then       // Does this user have the required permissions

9 文件索引←插入（文件表，inode编号）

9 file_index ← INSERT (file_table, inode_number)

10 fd ← FIND_UNUSED_ENTRY ( fd_table ) // 在文件描述符表中查找条目

10 fd ← FIND_UNUSED_ENTRY (fd_table)       // Find entry in file descriptor table

11 fd_table [ fd ] ← file_index        // 记录文件描述符的文件索引

11 fd_table[fd] ← file_index       // Record file index for file descriptor

12 返回 fd        // 返回fd

12 return fd       // Return fd

13 else return FAILURE        //否，返回失败

13 else return FAILURE       // No, return a failure

第2行查找文件filename的 inode 编号。如果文件不存在，但是调用者想要创建文件（如标志O_CREATE所示） （第3行），则OPEN调用CREATE，后者分配一个 inode、初始化它并返回其 inode 编号（第4行）。如果文件不存在（即使在尝试创建之后仍然存在），OPEN将返回一个表示失败的值（第6行）。第7行定位 inode。第8行使用 inode 中的信息检查调用者是否有权打开文件；该检查在第 11.6.3.4 节 [在线] 中详细描述。如果有，则第9行在文件表中为 inode 编号创建一个新条目，并将该条目的文件光标设置为零，将引用计数设置为 1。第10行查找第一个未使用的文件描述符，记录其文件索引，然后将该文件描述符返回给调用者（第 10至12行）。否则，它将返回一个表示失败的值（第13行）。

Line 2 finds the inode number for the file filename. If the file doesn’t exist, but the caller wants to create the file as indicated by the flag O_CREATE (line 3), OPEN calls CREATE, which allocates an inode, initializes it, and returns its inode number (line 4). If the file doesn’t exist (even after trying to create it), OPEN returns a value indicating a failure (line 6). Line 7 locates the inode. Line 8 uses the information in the inode to check if the caller has permission to open the file; the check is described in detail in Section 11.6.3.4 [on-line]. If so, line 9 creates a new entry for the inode number in the file table and sets the entry’s file cursor to zero and reference count to 1. Line 10 finds the first unused file descriptor, records its file index, and returns the file descriptor to the caller (lines 10 through 12). Otherwise, it returns a value indicating a failure (line 13).